Maintained by Vikas Dulgunde, software engineer
You begin standing on index 0 of an integer array. The number sitting at your current index is a ceiling, not a fixed distance: from index i you may land on any index between i+1 and i+nums[i]. Smaller hops are always allowed, so a value of 4 lets you advance one, two, three, or four positions in a single move.
Your goal is to count the smallest number of moves that gets you onto the final index. The problem promises the end is always reachable, so you never have to worry about getting stuck or returning a sentinel for failure.
Because every move can cover a range of landing spots, the interesting question is not whether you can finish but how to finish in as few hops as possible. Greedily reaching as far as you can with each jump turns out to be optimal, which is why this problem rewards thinking in terms of reachable windows rather than individual cells.
From index 0 you can reach index 1 or 2. Landing on index 1 (value 3) then lets you reach index 4 directly. Two jumps total. Going through index 2 would need a third jump, so two is the minimum.
The zero at index 2 is a dead spot, but you never have to step on it. Jump 0 to 1, then 1 to 4 using the stride of 3. The greedy window from the first jump already covers indices 1 through 2, and index 1 extends the reach all the way to the end.
Every value is 1, so each jump advances exactly one position. Reaching index 3 from index 0 takes three single steps.
Visible test cases
An element does not force you to jump its full value. From index i you can land anywhere in the range i+1 to i+nums[i], so think about the set of indices each jump unlocks rather than one destination.
Process the array left to right and track the farthest index you could reach if you take one more jump. The current jump covers a contiguous window of indices; you only spend a new jump when you step past the right edge of that window.
Keep three counters: the boundary of the current jump's window, the farthest index reachable so far, and the jump count. Increment jumps the moment your scan index hits the window boundary, then extend the boundary to the farthest reachable index.
Treat indices as nodes and each jump as moving one level deeper in a BFS. Every level is the set of indices reachable with the same number of jumps, so the level at which the last index first appears is the answer.
Walk through the array once while tracking the farthest reachable index. The current jump owns a window of indices; the instant your scan reaches the window's right edge you must have spent a jump, so bump the count and slide the window out to the farthest point seen so far.