codejump
MediumPythonJavaScriptTypeScript

Greedy — Jump Game II

AlgorithmsGreedyArrays

solve(nums) — same setup as Jump Game: nums[i] is the maximum jump length from
index i. The last index is always reachable. Return the **minimum number of
jumps** needed to get there.

Treat it as a BFS without a queue: the indices reachable with k jumps form a
window. When you leave the current window you must have made one more jump, and the
next window ends at the farthest index seen so far.

Examples

solve([2,3,1,1,4])       → 2     // 0 → 1 → 4
solve([2,3,0,1,4])       → 2
solve([0])               → 0
solve([1,1,1,1])         → 3
solve([5,1,1,1,1,1])     → 1

Sample tests

Test #1Classic example
Input: [[2,3,1,1,4]]
Output: 2
Test #2A zero in the middle
Input: [[2,3,0,1,4]]
Output: 2
Test #3Single cell
Input: [[0]]
Output: 0