LeetCode 55 – Jump Game

Jump Game is a greedy problem that spends most of its time disguised as a dynamic programming problem. Both solutions are short. One is O(n²) and the other is O(n), and the distance between them is a single change of viewpoint.

The problem

You start at index 0 of an integer array. nums[i] is the maximum jump length from index i — you may jump anywhere from 1 to nums[i] steps forward. Return whether the last index is reachable.

[2,3,1,1,4]  -> true    0 -> 1 -> 4
[3,2,1,0,4]  -> false   every route lands on index 3, whose 0 is a dead end
[0]          -> true    already at the last index; no jump needed
[1,0]        -> true
[0,1]        -> false

The word maximum is doing the work. If nums[i] were an exact jump length this would be a much harder problem. Because it is a ceiling, everything between you and i + nums[i] is reachable, and reachability turns out to be an interval rather than a set of scattered landing spots.

Why the obvious search is the wrong shape

The instinct is to explore: from index i, try every jump length, recurse. That is a DFS over a graph whose branching factor is nums[i], and without memoisation it is exponential — [5,4,3,2,1,0,0] will make you wait.

Memoising fixes the blowup and gives the honest DP: good[i] is true when some j in i+1 .. i+nums[i] is good, computed right to left. That is O(n²) and it will pass. But it answers a harder question than the one asked — it computes reachability for every index, when you were only asked about the last one.

One number is enough

Sweep left to right carrying a single value: the furthest index reached so far.

At index i, if i is beyond that furthest point, no earlier index could jump here, nothing further along can be reached either, and the answer is false. Otherwise i is standable-on, so update the furthest point to max(reach, i + nums[i]).

[3,2,1,0,4]

i=0  reach 0  ok    reach = max(0, 0+3) = 3
i=1  reach 3  ok    reach = max(3, 1+2) = 3
i=2  reach 3  ok    reach = max(3, 2+1) = 3
i=3  reach 3  ok    reach = max(3, 3+0) = 3
i=4  reach 3  4 > 3 -> false

Why is one number sufficient? Because reachability here has no holes. If you can reach index k, you can reach every index below it, since any jump can be shortened. The reachable set is always a prefix, and a prefix is fully described by its right-hand end. Say that sentence in the interview — it is the justification the greedy needs, and greedy answers without a justification are just guesses that happened to be right.

Java

class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;      // the furthest index reachable using indices seen so far

        for (int i = 0; i < nums.length; i++) {
            if (i > reach) return false;        // this index was never reachable

            reach = Math.max(reach, i + nums[i]);

            if (reach >= nums.length - 1) return true;   // early exit, optional
        }

        return true;
    }
}

i + nums[i] can exceed the array length, which is fine — it is compared, never used as an index. The early exit is a genuine optimisation on inputs like [100000,0,0,...,0], but the loop is correct without it, so add it after the plain version works.

Note reach starts at 0, not nums[0]. Index 0 is where you already are, and the first iteration applies its jump anyway. Seeding it with nums[0] would also work but reads as though it handles a case the loop does not.

Python

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        reach = 0

        for i, jump in enumerate(nums):
            if i > reach:
                return False
            reach = max(reach, i + jump)

        return True

A single-element array returns True without the loop body ever tripping the guard — you are already standing on the last index, and "no jump needed" is a valid win. Worth checking out loud, since it is the case a hand-written early return most often gets wrong.

The backward version

The same greedy read right to left, tracking the leftmost index known to reach the end. Some interviewers prefer it because the invariant is stated as a goal rather than a frontier:

        int leftmostGood = nums.length - 1;

        for (int i = nums.length - 2; i >= 0; i--) {
            if (i + nums[i] >= leftmostGood) {
                leftmostGood = i;      // from here you can land on a known-good index
            }
        }

        return leftmostGood == 0;

Identical complexity, same number of lines. Knowing both is cheap and being able to switch when asked "can you do it from the other end?" is worth the five minutes.

Complexity

The DP is O(n²) and not O(n) because the inner scan over i+1 .. i+nums[i] can be the length of the array. Mentioning it and then discarding it is a stronger answer than jumping straight to the greedy, because it shows the greedy was a choice.

The pattern

Jump Game II (45) asks for the minimum number of jumps, and the same frontier idea becomes a BFS counted in levels: track the end of the current jump's range and increment the counter when you reach it. Gas Station (134) is another one-pass greedy where a running total that dips below zero means "no valid start before here". Video Stitching (1024) and Minimum Number of Taps (1326) are the interval-covering versions of exactly this.

The family trait: a single scalar summarising everything the prefix has bought you, updated with a max, and a proof that the reachable set has no holes in it.

What the interviewer is checking

• That you notice nums[i] is a maximum, not an exact jump.
• That you can justify the greedy — reachability is a prefix — rather than assert it.
• That one variable replaces the whole good[] table.
• The i > reach guard, which is what makes [3,2,1,0,4] false.
• [0] returning true, and [0,1] returning false.
• That you mention the O(n²) DP and say why you are not using it.