DSA interview question

Jump Game II (Minimum Jumps)

Medium · Algorithms · Topics: greedy, array, dp

The problem

In the same platformer, the last tile is guaranteed reachable, and now the game wants the fewest jumps needed. Think of it as BFS by levels without a queue. All tiles reachable with j jumps form a contiguous range. The next range extends to the farthest i + nums[i] from any tile in the current range. Each time the scan crosses the end of the current range, one more jump is needed.

Example: [2, 3, 1, 1, 4] → 2 (0 → 1 → 4).

Function signature

int jump(const vector<int>& nums);  // the last index is guaranteed reachable

Test cases

Input	Output	Explanation
`[2, 3, 1, 1, 4]`	`2`	0 → 1 → 4
`[2, 3, 0, 1, 4]`	`2`
`[0]`	`0`	Already there
`[1, 1, 1, 1]`	`3`
`[10, 1, 1]`	`1`	One big jump

(Confirm: jumps are 1 to nums[i] long; the input always allows reaching the last index.)

How interviewers phrase it

"Return the minimum number of jumps to reach the last index; you can always reach it" (LeetCode 45).

Clarifying questions to ask

Is the end guaranteed reachable? (Yes.)
Do I need the path or just the count? (Just the count.)
How large is n? (Up to 10⁴, so O(n) is expected.)

Follow-ups to expect

"Why is this BFS?"
"What do currentEnd and farthest mean?"
"Why stop the loop at n − 2?"
"DP alternative?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview