Skip to main content

45. Jump Game II

medium

Minimum number of jumps to reach the last index. A BFS-style 1D greedy — track the current jump's reach and the next jump's reach as two rolling pointers.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where: 0 <= j <= nums[i] and i + j < n. Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Constraints

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

Examples

Example 1

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

Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

BFS interpretation: layer k contains every index reachable in exactly k jumps.

Hint 2

Track current_end (last index reachable in the current layer) and farthest (max next-layer reach).

Hint 3

When i reaches current_end, commit a jump (jumps += 1) and set current_end = farthest.

Solution approach

Reveal approach

BFS-greedy implicit layering. Maintain three values: jumps = number of jumps used so far; current_end = last index reachable within those jumps; farthest = the furthest index reachable using one more jump. Sweep i from 0 to n-2 (skip the last index — landing there counts). At each i, farthest = max(farthest, i + nums[i]). When i == current_end, you've exhausted the current layer — commit: jumps += 1; current_end = farthest. If current_end >= n - 1, break early. Return jumps. O(n) time, O(1) space. The 1D DP equivalent is dp[i] = min jumps to reach i, but the greedy is strictly better.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • greedy
  • bfs

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Apple

More DP 1D practice problems

See all DP 1D problems →