Jump Game II

The key idea

Think in jump layers, like breadth-first search. Every index you can reach with k jumps forms one layer. While scanning the current layer, track the farthest index any of its members can reach. When you step past the end of the current layer you must spend one more jump, and the next layer extends out to that farthest reach. Counting how many times the layer boundary is crossed gives the minimum jumps.

Problem

You are given a 0-indexed array of integers nums of length n. You start at index 0.

Each element nums[i] represents the maximum forward jump length from index i. In other words, if you are at index i, you can jump to any index j such that i < j <= i + nums[i] and j < n.

Return the minimum number of jumps needed to reach index n - 1. The test cases are generated so that you can always reach the last index.

Constraints

1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
It is guaranteed that you can reach nums[n - 1].

Examples

Input: nums = [2,3,1,1,4] Output: 2

Input: nums = [2,3,0,1,4] Output: 2

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →