MediumGreedy · Dynamic Programming · BFS

Jump Game II

From index i you can jump right by up to nums[i]. Starting at index 0, return the minimum number of jumps to reach the last index. A valid answer always exists.

nums = [2,4,1,1,1,1] → 2 (0 → 1 → 5)nums = [2,1,2,1,0] → 2

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

The array

Arcs = possible jumps; the label under each cell is its jump count

Time and space complexity

n = len(nums). The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. Integers from 0 to 99; drawings use at most 10 numbers for top-down DP, 12 for bottom-up DP and 14 for greedy.