Greedy
Counting steps without a queue
Breadth-first search over an array, where each level is a contiguous stretch and needs no queue at all.
Key idea
This is a shortest-path problem
Asking for the fewest jumps is asking for the shortest path in an unweighted graph, where positions are nodes and a jump is an edge. Unit 12 says that is breadth-first search.
That works and it builds a queue. On an array there is a structural fact that removes the queue entirely: everything reachable in exactly k steps forms one contiguous stretch of positions.
Why it works
Why each level is contiguous
Positions reachable in one step form a stretch starting at the beginning. Anything reachable in two steps is reachable from somewhere in that stretch, and since jumps can be any length up to their maximum, every position between is also reachable.
So a level is fully described by two numbers: where it ends and where the next one ends. No queue, no visited set, two variables.
Below, the levels are worked out by hand for one input, so that the two numbers can be seen before any loop is written.
Gotcha
The loop stops one short of the end
The range excludes the final position. Standing on the end means you have arrived, so counting a jump there would return one too many.
That single omission is the most common error in this problem, and it only shows when the last position happens to coincide with a level boundary. Test with an input where it does.
Why it works
The increment happens at the boundary, not at every step
The step count rises only when the walk reaches the end of the current level, which is the moment another jump becomes unavoidable. Between boundaries, positions are all reachable with the same count and cost nothing extra.
That is the queue-free version of Unit 8's level batching, where the queue length was snapshotted to mark a level. Here the boundary is a position rather than a count, and the effect is the same.
Edge cases
This version assumes the end is reachable
The function counts jumps and never checks reachability. Most versions of this problem promise the end can be reached, which is why that is acceptable.
If the promise is absent, combine it with the previous lesson's stranded check. Notice which problem gives which guarantee rather than assuming, since the two problems are otherwise nearly identical.
Cost
Cost
One pass, constant work, so O(n) time and O(1) space. The queue-based search is also O(n) time and uses O(n) space for the queue and visited set.
Same asymptotic time, meaningfully less memory, and considerably shorter. The contiguity of levels is what buys it, and that fact is specific to this structure rather than general to graphs.
Where should the walk stop?
The walk spends a jump each time it reaches the end of the current level. On an input of n positions, which range should it walk, and why?
Jump Game Ii
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.