55. Jump Game

Jump Game looks like it wants you to search every path you could jump along — and if you reach for DP, you will. The greedy insight is that you never need the paths at all, just one number: how far you can currently get. It belongs to the greedy algorithms pattern, where a single forward-looking quantity replaces a full search.

The problem

You start at index 0 of an array, and each value tells you the maximum number of steps you may jump forward from that spot. The question is a yes/no: can you get to the last index? (Full statement on LeetCode.)

For [2, 3, 1, 1, 4] the answer is true — jump 1 to index 1, then 3 straight to the end. For [3, 2, 1, 0, 4] it’s false: whatever you do, you land on the 0 at index 3 and stall.

Intuition: carry the farthest index you can reach

Here’s the move that collapses the whole search. Instead of asking “which sequence of jumps works,” walk left to right and keep a single value — the farthest index reachable so far. Call it maxReach.

At each index i, one question decides everything: is i still within reach? If $i > \text{maxReach}$, no jump landed you here, so the end is unreachable — return false. Otherwise you can stand on i, so update your horizon:

$\text{maxReach} = \max(\text{maxReach},\; i + \text{nums}[i])$

If you walk off the end of the array without ever falling behind, the last index was reachable the whole time. The reason greedy is safe here: extending maxReach as far as possible never rules out a position a shorter jump would have reached, because reachability is contiguous — if you can reach index i, you can reach everything up to maxReach.

That’s also why the zeros matter. A 0 doesn’t fail on its own; it only bites when maxReach hasn’t already jumped past it by the time you arrive.

Solution

One pass, one variable:

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;                      // farthest index reachable so far
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false;    // fell behind — a zero (or gap) trapped us
            maxReach = Math.max(maxReach, i + nums[i]);
            // small optimization: once we can reach the end, we're done
            if (maxReach >= nums.length - 1) return true;
        }
        return true;
    }
}

The brute-force alternative is the $O(n^2)$ DP you might write first: a boolean[] dp where dp[i] marks reachable indices, filled by scanning every earlier reachable j with j + nums[j] >= i. It’s correct and more intuitive, but it recomputes reachability the greedy pass already tracks for free.

Complexity

Approach	Time	Space
Greedy (max reach)	$O(n)$	$O(1)$
DP (boolean[])	$O(n^2)$	$O(n)$

The greedy version touches each index once and keeps nothing but an int.

In an interview

Start by naming what you don’t need: not the path, not the number of jumps, just whether the end is reachable. That reframing is what unlocks the one-variable greedy — say it out loud before you write the loop. The trap interviewers plant is the trailing 0 ([3, 2, 1, 0, 4]): a candidate who only checks the last value misses that the 0 sits mid-array and cuts the reach. Walk that case and show maxReach freezing at 3 while i marches past it.

If they ask for the follow-up — Jump Game II, which counts the minimum jumps — the same reachability idea turns into a level-by-level greedy over the current horizon. The “one forward-looking quantity” habit is the throughline of the greedy algorithms pattern.

References

• LeetCode 55 — Jump Game