MediumArrayDynamic ProgrammingGreedyUpdated Sep 2026

45. Jump Game II

Asked at Google, Atlassian, Oracle, Salesforce

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

4

Problem

You are given an array nums of non-negative integers. You start at index 0. The value nums[i] is the maximum jump length you may take from index i. So from index i you can land on any index i + j where 0 <= j <= nums[i] and i + j < n.

Your goal is to reach the last index, n - 1, using the fewest possible jumps. Return that minimum number of jumps as an integer.

You may always assume the last index is reachable. If the array has only one element, you are already at the last index, so the answer is 0.

Jump ranges from each index

numsreachable in 1 jump2311401234Start at index 0 (orange). One jump can land on index1 or 2 (blue). The target is index 4 (green).numsreachable in 2 jumps2311401234From index 1, nums[1] = 3 lets you jump straight toindex 4. So 2 jumps is enough.
From index 0 you may reach indices 1 and 2. From index 1 you may reach index 4, the last index.

Constraints

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

Examples

Example 1
Inputnums = [2,3,1,1,4]
Output2
WhyFrom index 0 you can jump up to 2 steps. Jump 1 step to index 1, then from index 1 you can jump up to 3 steps, which lands you on index 4 (the last index). That is 2 jumps, and no single jump can cover the whole array.
Example 2
Inputnums = [2,3,0,1,4]
Output2
WhyAgain jump from index 0 to index 1, then from index 1 jump 3 steps to index 4. Index 2 holds 0, so landing there would trap you, but the greedy path avoids it.

Asked At

4 companies
CompanyDifficulty
GoogleMediumView all Google questions →
AtlassianMediumView all Atlassian questions →
OracleMediumView all Oracle questions →
SalesforceMediumView all Salesforce questions →

How to Think About It

1

BFS/greedy approach: treat each position as a level. From all positions reachable at the current jump, compute all positions reachable in one more jump. The first time you reach the last index is the minimum jumps.

2

Optimized greedy: track the farthest reachable index and the end of the current jump range. When you reach the end of the range, you must jump (increment jumps) and extend the range to the farthest reachable.

3

Why it works: at each jump, you consider all positions reachable from the current range. The farthest any of them can reach is the boundary of the next range. You only jump when forced (at the current range boundary).

4

Edge cases: single element (0 jumps), array starting at the last index (0 jumps), all ones (n-1 jumps).

Optimal Approach

Step 1: If nums has 1 or fewer elements, return 0.
Step 2: Initialize jumps = 0, currentEnd = 0, farthest = 0.
Step 3: For i from 0 to n-2:

  • farthest = max(farthest, i + nums[i])
  • If i == currentEnd:
    • jumps += 1
    • currentEnd = farthest
    • If currentEnd >= n-1, break
      Step 4: Return jumps.

The key insight: you only increment jumps when you reach the boundary of the current range. At that point, you extend the range to the farthest point reachable from any position in the current range.

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

Greedy level-by-level scan

numscurrentEnd = 02311401234iStart: jumps = 0, currentEnd = 0, farthest = 0. i = 0hits currentEnd, so we must jump.numscurrentEnd = 22311401234iAfter the jump: jumps = 1, farthest = 0 + nums[0] = 2,so currentEnd = 2. Now scan indices 1 and 2.numscurrentEnd = 42311401234iAt i = 1, farthest = max(2, 1 + 3) = 4. At i = 2 wehit currentEnd again, so jumps = 2 and currentEnd = 4,which is the last index.farthest = max(farthest, i + nums[i])if i == currentEnd: jumps++, currentEnd = fartheststop when currentEnd >= n - 1
Track the farthest index you can reach and the end of the current jump range. Jump only when you hit that end.
ComplexityTime O(n)Space O(1)One left-to-right pass over the array, keeping only a few integer variables.

What Trips People Up in Real Interviews

1

Confusing Jump Game II (minimum jumps) with Jump Game (just reachable). The first requires counting jumps with greedy BFS, the second only checks if the last index is reachable.

2

Using BFS level-by-level without tracking the current range boundary. The optimized greedy approach only increments jumps when you reach currentEnd, not at every position.

3

Advancing mid (or the loop index) when swapping with high in a two-pointer variant. In this greedy approach there is no such swap, but candidates often mix it up with sort-colors logic.

4

Forgetting that the farthest reachable index must be updated at every position, not just when a jump occurs. If you only update farthest at the boundary, you miss better reach from later indices.

5

Not handling the edge case where nums[0] is already large enough to reach the end in one jump. The loop should break early when currentEnd >= n - 1.

Solution Code

O(n) time
def jump(nums):
    if len(nums) <= 1:
        return 0
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
            if current_end >= len(nums) - 1:
                break
    return jumps

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Jump Game II problem?

Given an integer array nums where nums[i] represents the maximum jump length from position i, reach the last index in the minimum number of jumps. You can assume you can always reach the last index.

How do you solve Jump Game II?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Jump Game II?

Jump Game II is asked at Google, Atlassian, Oracle, Salesforce. It is a medium difficulty problem.

What are common mistakes on Jump Game II?
  • Confusing Jump Game II (minimum jumps) with Jump Game (just reachable). The first requires counting jumps with greedy BFS, the second only checks if the last index is reachable.
  • Using BFS level-by-level without tracking the current range boundary. The optimized greedy approach only increments `jumps` when you reach `currentEnd`, not at every position.
  • Advancing `mid` (or the loop index) when swapping with `high` in a two-pointer variant. In this greedy approach there is no such swap, but candidates often mix it up with `sort-colors` logic.
  • Forgetting that the farthest reachable index must be updated at every position, not just when a jump occurs. If you only update `farthest` at the boundary, you miss better reach from later indices.
  • Not handling the edge case where `nums[0]` is already large enough to reach the end in one jump. The loop should break early when `currentEnd >= n - 1`.