Jump Game

PracticeNeetCode ↗LeetCode ↗

Given an integer array nums where each element is the maximum jump length from that position, determine whether you can reach the last index starting from index 0.

Example

Key Pointers

• Track the furthest index reachable so far instead of simulating every possible jump path.
• If the current index ever exceeds the furthest reachable index, that position is unreachable and the answer is false.
• A single greedy left-to-right pass is enough — no need to try every jump length from every position.

Step-by-Step Analysis

1. Initialize farthest = 0.
2. For each index i, value n in nums: if i > farthest, return False — this index can't be reached.
3. Otherwise update farthest = max(farthest, i + n).
4. If the loop completes, return True.

Complexity

Time: O(n) — Space: O(1)

Code

def canJump(nums: list[int]) -> bool:
    farthest = 0
    for i, n in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + n)
    return True

Code Explanation

How the solution above works, piece by piece.

1. farthest = the furthest index reachable so far.
2. Walk left to right. If i > farthest, index i can't be reached, so neither can the end → False.
3. Otherwise, from i you can reach i + nums[i]; update farthest.
4. If the loop finishes, every index (including the last) was reachable → True.
5. One pass, O(1) space: no need to know which jumps, only how far they can get.

Visual Walkthrough

Running it on nums = [2, 3, 1, 1, 4]:

Video Explanation

NeetCode — Greedy, LeetCode 55