LeetCode #55 Medium

Jump Game

Each element is the maximum jump length from that position. Starting at index 0, return whether you can reach the last index.

greedyarray

Open on LeetCode ↗

02

Intuition

💡

First, kill the assumption that sinks most attempts: nums[i] is the maximum you may jump, not the amount you must. You are free to jump shorter, so a big value never forces you past a useful landing spot. Once that is clear, you never need to know how you reached an index, only whether you could — so track the furthest index reachable so far and walk left to right. The whole problem then reduces to one question: is there a zero you cannot jump over?

03

Approach

1

Start from the brute force and see the waste

From index i you may jump 1, 2, ..., nums[i] steps — any of them, which is exactly the point people miss. Recursion explores each branch separately, but two jump sequences landing on the same index face an identical remaining problem. Memoising gives O(n^2); the greedy view removes the table entirely by noticing that the set of reachable indices is always a prefix.

2

Track one number: the furthest reach

Because you can jump any distance up to nums[i], everything between the current position and i + nums[i] is reachable. So the reachable set is never scattered — it is always a contiguous prefix, fully described by its right edge. Keep maxReach = max(maxReach, i + nums[i]) as you scan.

3

The only failure is a gap

Walk i from 0 upward. If i > maxReach, nothing earlier can land here or beyond — return false. In practice this fires at exactly one kind of place: a zero, or a run leading into one, that the accumulated reach never clears. That is the whole catch of the problem. Everything else extends the reach, and once maxReach covers the last index you can stop. One pass, O(n) time and O(1) space.

04

Solution & live demo

python

▶1class Solution:
▶2    def canJump(self, nums):
▶3        maxReach = 0
▶4        for i, step in enumerate(nums):
▶5            if i > maxReach:
▶6                return False
▶7            maxReach = max(maxReach, i + step)
▶8            if maxReach >= len(nums) - 1:
▶9                break
▶10        return True

05

Edge cases

Single element array

You already stand on the last index, so the answer is true without any jump.

A zero at the last index

Harmless — you only need to reach it, not jump from it.

A zero mid-array that is jumpable

Fine, since an earlier index may reach past it; the running maximum captures exactly this.

First element is 0 with n > 1

maxReach stays 0 while i becomes 1, so the gap check fires immediately and returns false.

06

Complexity

Time

O(n)

Space

O(1)

One pass and a single integer. The O(n^2) DP is what this replaces.