Jump Game II

Given an array where each element represents your maximum jump length from that position, return the minimum number of jumps needed to reach the last index (a valid path is always guaranteed to exist).

MediumRecommendedGreedy Array Patterns

Solve This Problem

Video Solution

Video coming soon

We're producing a video walkthrough — check back soon.

Problem Overview

Why solve this?

Builds directly on Jump Game's reachability idea, but now counts jumps — the greedy strategy reframes the array into levels, similar in spirit to how BFS explores a graph layer by layer, without needing an actual queue.

Pattern Recognition

When a reachability-style greedy problem is extended to ask for the minimum number of steps, look for a way to process the array in ranges or levels, advancing to the next range only once the current one is exhausted — a greedy stand-in for BFS layers.

Prerequisites

Jump Game — this problem reuses the farthest-reachable-index idea, now counting how many jumps it takes to extend that boundary all the way to the end.

Hints

Think of the array as a sequence of ranges — everything reachable within the current number of jumps.
Track three values: the end of the current range, the farthest index reachable using one more jump, and the jump count.
Every time you reach the end of the current range, that's forced — you must take another jump, so increment the count and extend the range to the farthest index found so far.

Approach

Process the array in ranges reachable by an increasing number of jumps, similar to BFS levels. Track currentRangeEnd (the farthest index reachable with the jumps taken so far), farthest (the farthest index reachable with one additional jump from anywhere in the current range), and jumps (the count so far). Scan the array: at each index, update farthest to the largest index-plus-jump-length seen. When the scan reaches currentRangeEnd — meaning every option within the current number of jumps has been explored — increment jumps and extend currentRangeEnd to farthest. The scan stops once currentRangeEnd reaches or passes the last index. Because the problem guarantees the last index is always reachable, no reachability check is needed here, unlike Jump Game.

Code

Solution.java

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

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