Jump Game

MediumGreedy · Reachability🧩 Greedy LeetCode #55 ↗Updated Oct 30, 2026

Problem

You start at index 0 of an integer array nums. The value nums[i] is the maximum number of steps you may jump forward from index i (any smaller jump is also allowed). Return true if the last index can be reached, otherwise false.

Inputnums = [2,3,1,1,4]Outputtrue (0 → 1 → 4)

Inputnums = [3,2,1,0,4]Outputfalse (every path lands on the 0 at index 3)

Inputnums = [0]Outputtrue

1 ≤ n ≤ 10⁴ · 0 ≤ nums[i] ≤ 10⁵

Try it yourself

Java

class Solution {
    public boolean canJump(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

You never need to know which path works — only the farthest index reachable so far. Every index up to that frontier is reachable, so sweep once and extend the frontier; if you ever stand beyond it, you're stuck.

PatternGreedy

Instinct An optimisation where one obvious local rule (earliest end, farthest reach, biggest first) never needs undoing - commit to it, then try hard to break it.

Memory hack Grab the best bite now and never look back - but only once a counterexample hunt fails to make you regret it.

Open the Greedy guide →

Approaches

Brute ForceTry Every Jump (Recursion)

Time O(2ⁿ)Space O(n)

From index i, try every jump length 1..nums[i] and recurse. If any branch lands on the last index, the answer is yes. Without memory the same index is re-solved again and again, so the number of paths explodes.

Java

public boolean canJump(int[] nums) {
    return reach(nums, 0);
}

private boolean reach(int[] nums, int i) {
    if (i >= nums.length - 1) return true;
    int farthest = Math.min(i + nums[i], nums.length - 1);
    for (int next = farthest; next > i; next--) { // try long jumps first
        if (reach(nums, next)) return true;
    }
    return false;
}

Direct translation of the rules; exponential, only usable for tiny arrays.

BetterBottom-Up DP over Good Indices

Time O(n · max(nums))Space O(n)

Call an index good if the end is reachable from it. The last index is good; scanning right to left, index i is good if any index within its jump range is good. Each index is solved once, so repeated work disappears — but each still scans up to nums[i] neighbours (O(n²) in the worst case).

Java

public boolean canJump(int[] nums) {
    int n = nums.length;
    boolean[] good = new boolean[n];
    good[n - 1] = true;
    for (int i = n - 2; i >= 0; i--) {
        int farthest = Math.min(i + nums[i], n - 1);
        for (int j = i + 1; j <= farthest; j++) {
            if (good[j]) {
                good[i] = true;
                break;
            }
        }
    }
    return good[0];
}

Polynomial and easy to justify, but still re-scans overlapping ranges.

OptimalGreedy Farthest Reach

Time O(n)Space O(1)

Keep reach = farthest index reachable from anything seen so far. Walk left to right: if i > reach, index i is unreachable and so is everything after it. Otherwise extend reach with i + nums[i]; once it covers the last index we're done.

Java

public boolean canJump(int[] nums) {
    int reach = 0; // farthest index reachable so far
    for (int i = 0; i < nums.length; i++) {
        if (i > reach) return false;              // stuck before i
        reach = Math.max(reach, i + nums[i]);
        if (reach >= nums.length - 1) return true; // end is covered
    }
    return true;
}

Dry runnums = [2,3,1,1,4]

i indexR reach changed

i=0
3
i
2

1

0
R
4

reach=0+3=3
i=1
3

2
i
1

0
R
4

1+2=3, reach 3
i=2
3

2

1
i
0
R
4

2+1=3, reach 3
i=3
3

2

1

0
i R
4

3+0=3, reach 3
i=4
3

2

1

0
R
4
i
4 > reach → false

One pass, constant memory — the expected interview answer.

Pro tip

Equivalent backward view: move a goal left whenever i + nums[i] ≥ goal; answer is goal == 0.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Jump (Recursion)	`O(2ⁿ)`	`O(n)`
Better	Bottom-Up DP over Good Indices	`O(n · max(nums))`	`O(n)`
Optimal	Greedy Farthest Reach	`O(n)`	`O(1)`

Common pitfalls

Only trying the maximum jump each time — a shorter jump may be the one that works.
Forgetting that a single-element array is already at the end (true).
Checking i > reach after updating reach — lets you jump from an unreachable cell.

Interview tips

Start with the recursion tree, point out repeated sub-problems, then move to DP.
Explain why tracking one number suffices: reachable indices form a prefix.
Mention Jump Game II (min jumps) uses the same frontier idea, BFS-by-layers style.

Pattern

Greedy frontier → when reachable states always form a contiguous prefix, track only its right edge.

My notes saved in this browser