Jump Game

MEDIUM✓ CHIP-TIMEDLC #55 — FULL STATEMENT ↗

The drill: Starting at the first index of an array where each value caps how far a single jump may go from there, decide whether some sequence of forward hops can reach the last index.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of non-negative integers stands for a row of positions, starting at the first one. Each position's value is the farthest single jump allowed from there — any shorter hop from that position is fine too.

Starting from index zero, the question is whether some sequence of forward hops, each respecting its launch position's cap, can land exactly on the final index of the array.

The answer needed is just a yes-or-no verdict on reachability — not the actual sequence of hops that gets there.

EX 01

nums = [2, 0, 0, 1, 4]

→ false

STALLS TWO ZEROS SHORT OF THE LAST STRETCH

EX 02

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

→ false

CLASSIC TRAP AT THE ZERO

EX 03

nums = [1, 1, 1, 1]

→ true

SINGLE STEPS, JUST BARELY ENOUGH

the array always has at least one position, the starting one
jump lengths are non-negative, and zero means stuck at that spot
hops only move forward, never backward
only reachability of the last index matters, not the path taken

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A hop of length k from index i really means 'any hop of length 1..k is available.' So instead of asking which exact hops to take, ask a simpler question: which indices are reachable at all?

HINT 2 THE STRUCTURE

Track the single farthest index reachable so far as you scan left to right. If you ever land on a position beyond that farthest point before it gets extended, nothing after that can save you.

HINT 3 ONE STEP FROM THE ANSWER

One pass: maxReach = max(maxReach, i + nums[i]) at every i, but only while i itself is still within maxReach — the moment i outruns maxReach, the array is unreachable from there.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FARTHEST RUNPATTERN · GREEDY — FARTHEST REACHnums = [3, 2, 1, 0, 4]

FARTHEST REACH

maxReach → 0

STEP 1

Values [3, 2, 1, 0, 4] cap each hop's length. maxReach starts at 0 — the farthest index reachable so far.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/jump-game.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        maxReach = 0
        for i, num in enumerate(nums):
            if i > maxReach:
                return False
            maxReach = max(maxReach, i + num)
        return True

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

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        reachable = [False] * n
        reachable[0] = True
        for i in range(n):
            if not reachable[i]:
                continue
            for step in range(1, nums[i] + 1):
                if i + step < n:
                    reachable[i + step] = True
        return reachable[n - 1]

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

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]);
        }
        return true;
    }
}

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

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] reachable = new boolean[n];
        reachable[0] = true;
        for (int i = 0; i < n; i++) {
            if (!reachable[i]) {
                continue;
            }
            for (int step = 1; step <= nums[i]; step++) {
                if (i + step < n) {
                    reachable[i + step] = true;
                }
            }
        }
        return reachable[n - 1];
    }
}

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

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