Jump Game

MediumGreedyBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an integer array nums. You start at index 0, and nums[i] is the maximum jump length from index i: from there you may move forward by any number of steps from 1 up to nums[i], and a 0 means you can't move on from that spot. Return true if you can reach the last index, and false otherwise.

Examples

nums = [2,3,1,1,4] returns true

Jump 1 step from index 0 to index 1, then 3 steps from index 1 straight to index 4, the last index.

nums = [3,2,1,0,4] returns false

Every route gets to index 3 at best, and nums[3] is 0, so you can never get past it to index 4.

nums = [0] returns true

With a single element you already stand on the last index, so no jump is needed.

Constraints

1 <= nums.length <= 10^4

Hints

Hint 1

Instead of trying every jump, what if you only tracked the farthest index you can currently reach?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

You don't need to track actual jumps, only reach, the farthest index any path could get to so far. Scan left to right: if i is beyond reach, no earlier index can land on i, so return false. Otherwise extend reach to max(reach, i + nums[i]). Every index up to reach is reachable, because a shorter jump is always allowed. If the scan finishes, the last index was within reach.

Time

O(n)

Space

O(1)

Pitfall

Treating every 0 as a dead end is wrong: in [2,0,1] you simply jump over the 0. The real failure is arriving at an index i > reach, which no earlier position can land on.

Solutions

class Solution {
    public 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]);
        }
        return true;
    }
}

class Solution:
    def canJump(self, nums) -> bool:
        reach = 0
        for i, n in enumerate(nums):
            if i > reach:
                return False
            reach = max(reach, i + n)
        return True