Jump Game

mediumGreedy & Intervals11 stepsJava · Python · C++

Each value is the maximum jump from that index. Can you reach the end? Track the farthest index reachable so far. If you ever stand on an index beyond it, you're stuck.

▶ Watch the animated trace

Traced input: nums = [2, 3, 1, 1, 4] → true. Original problem: neetcode.io/problems/jump-game

Complexity

BestO(1)

AverageO(n)

WorstO(n)

SpaceO(1)

Stops as soon as the end is reachable.

Key idea

reach = max(reach, i + nums[i]) for every index you can stand on.
If i > reach, index i can't be reached, and neither can anything after it.
No need to know which jumps to take.

Common mistakes

BFS or DP over all jumps is O(n²).
Treating a 0 at the last index as a problem; you're already there.

Solution

Java

boolean canJump(int[] nums) {
    int reach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > reach) {
            return false;
        }
        reach = Math.max(reach, i + nums[i]);
        if (reach >= nums.length - 1) {
            return true;
        }
    }
    return true;
}

Python

def canJump(nums: List[int]) -> bool:
    reach = 0
    for i, x in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + x)
        if reach >= len(nums) - 1:
            return True
    return True

C++

bool canJump(vector<int>& nums) {
    int reach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > reach) {
            return false;
        }
        reach = max(reach, i + nums[i]);
        if (reach >= (int)nums.size() - 1) {
            return true;
        }
    }
    return true;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Stuck on a zero Every path lands on index 3, which can't move.	`nums = [3, 2, 1, 0, 4]`	`false`
Single element You start at the end.	`nums = [0]`	`true`
Zero at the start You can't leave index 0.	`nums = [0, 1]`	`false`
Big first jump The first jump covers everything.	`nums = [5, 0, 0, 0, 0]`	`true`