Command Palette

Search for a command to run...

Hectal
Problem 33.3 · Greedy AlgorithmsMedium

Jump Game II

PatternGreedy ChoiceGraph BFS

What it teaches: Implicit BFS levels: each range of reachable indices costs one jump.

Practise it on judges as “Jump Game II”.

The problem

Return the minimum number of jumps to reach the last index (it's always reachable).

Example 1

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

Constraints

  • 1 ≤ n ≤ 10⁴

Pattern clues in the wording

  • → Fewest jumps

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int jump(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [2,3,1,1,4]
2
2
nums = [2,3,0,1,4]
2
3
nums = [0]
0

From slow to fast

Approaches

1. Level-by-level reach · O(n)
1

Level-by-level reach

Time O(n) Space O(1)

For i < n − 1: farthest = max(farthest, i + nums[i]); if i == end, jumps++ and end = farthest.

Approach 1
class Solution {
    public int jump(int[] nums) {
        int jumps = 0, end = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == end) { jumps++; end = farthest; }
        }
        return jumps;
    }
}

Verdict: BFS without a queue.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Single element (0)
  • First jump reaches the end

Mistakes people make

  • Looping to the last index (counts an extra jump).

Interview

Follow-up questions

Why is it BFS?