Jump Game II

MEDIUM✓ CHIP-TIMEDLC #45 — FULL STATEMENT ↗

The drill: From the first index, each value caps how far a single jump may travel. Find the fewest jumps needed to land exactly on the last index — a path there always exists.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Same setup as a single hop of forward jumping: an array of non-negative integers where each position's value caps how far one jump from there can travel, starting at index zero.

This time a path to the last index is always possible, and the question shifts from whether to how few — find the minimum number of jumps needed to land exactly on the final index.

Any hop shorter than a position's cap is legal too, so intermediate landing spots are flexible; only the total jump count of the best path is the answer.

EX 01

nums = [1, 2, 1, 1, 1]

→ 3

0 -> 1 -> 3 -> 4

EX 02

nums = [1, 1, 1, 1]

→ 3

FORCED SINGLE STEPS THROUGHOUT

EX 03

nums = [3, 1, 1, 1, 1, 1]

→ 3

BIG FIRST JUMP, THEN TWO FORCED STEPS

the array always has at least one position, the starting one
a path to the final index is always guaranteed to exist
hops only move forward, and any length up to the cap is legal
only the minimum jump count is reported, not the path itself

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A single jump of length k really offers k different landing spots. Instead of tracking every possible position after each jump, ask: what's the farthest ANY jump from ANY position I can currently reach could get me?

HINT 2 THE STRUCTURE

Group positions into 'waves' — everything reachable in exactly k jumps. The moment your scan passes the current wave's boundary, you've stepped into the next wave.

HINT 3 ONE STEP FROM THE ANSWER

Track farthest (the best reach seen so far) and curEnd (the current wave's boundary). When your scan index reaches curEnd, that wave is exhausted — increment jumps and set curEnd = farthest.

COACH'S BOARD — THE PATTERN, STEP BY STEP

WAVES OF REACHPATTERN · GREEDY — IMPLICIT BFS BY WAVESnums = [1, 2, 1, 1, 1]

JUMPS · CUREND · FARTHEST

jumps → 0

curEnd → 0

farthest → 0

STEP 1

Values [1, 2, 1, 1, 1] cap each hop. jumps, curEnd, and farthest all start at 0 — wave zero is just index 0.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/jump-game-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = curEnd = farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == curEnd:
                jumps += 1
                curEnd = farthest
        return jumps

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 9 LN

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [math.inf] * n
        dp[0] = 0
        for i in range(n):
            reach = min(i + nums[i], n - 1)
            for j in range(i + 1, reach + 1):
                dp[j] = min(dp[j], dp[i] + 1)
        return dp[n - 1]

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 10 LN

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

TIME O(N)SPACE O(1)JAVA · RACE PACE · 13 LN

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int reach = Math.min(i + nums[i], n - 1);
            for (int j = i + 1; j <= reach; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED