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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Jump Game II and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →