Jump Game

Difficulty: Medium Source: NeetCode

Problem

You are given an integer array nums. You are initially positioned at the first index. Each element nums[i] represents your maximum jump length from that position. Return true if you can reach the last index.

Example 1: Input: nums = [2, 3, 1, 1, 4] Output: true

Example 2: Input: nums = [3, 2, 1, 0, 4] Output: false Explanation: You always land on index 3 which has jump length 0.

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy algorithms — tracking the farthest reachable index
• Sliding window / scan — linear pass through the array

1. Brute Force / BFS

Intuition

Model this as a graph problem. From index i, you can jump to any index from i+1 to i + nums[i]. Do a BFS/DFS from index 0 and check if n-1 is reachable. This works but is slow due to revisiting indices.

Algorithm

1. Use a set reachable initialised with {0}.
2. For each index i in reachable:
   • Add all indices from i+1 to i + nums[i].
3. Return n-1 in reachable.

Solution

def canJump(nums):
    n = len(nums)
    reachable = {0}
    queue = [0]

    while queue:
        i = queue.pop(0)
        for j in range(i + 1, min(i + nums[i] + 1, n)):
            if j not in reachable:
                if j == n - 1:
                    return True
                reachable.add(j)
                queue.append(j)

    return (n - 1) in reachable


print(canJump([2, 3, 1, 1, 4]))   # True
print(canJump([3, 2, 1, 0, 4]))   # False
print(canJump([0]))                # True
print(canJump([1, 0, 0]))          # False

Complexity

• Time: O(n²) — each index can be visited and expanded
• Space: O(n) — reachable set

2. Greedy — Track Maximum Reachable Index

Intuition

Scan left to right, tracking the farthest index we can reach (max_reach). At each index i, if i > max_reach, we’re stuck — we can’t even get to i, so return false. Otherwise, update max_reach = max(max_reach, i + nums[i]). If we finish the loop without getting stuck, we can reach the end.

Algorithm

1. Initialise max_reach = 0.
2. For each index i from 0 to n-1:
   • If i > max_reach, return False.
   • max_reach = max(max_reach, i + nums[i]).
3. Return True.

Solution

def canJump(nums):
    max_reach = 0

    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])

    return True


print(canJump([2, 3, 1, 1, 4]))   # True
print(canJump([3, 2, 1, 0, 4]))   # False
print(canJump([0]))                # True
print(canJump([1, 0, 0]))          # False
print(canJump([2, 0, 0]))          # True (can jump from 0 to 2)


# Alternative: scan from right (DP-like)
def canJump_right(nums):
    goal = len(nums) - 1
    for i in range(len(nums) - 2, -1, -1):
        if i + nums[i] >= goal:
            goal = i
    return goal == 0


print(canJump_right([2, 3, 1, 1, 4]))   # True
print(canJump_right([3, 2, 1, 0, 4]))   # False

Complexity

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

Common Pitfalls

Returning False when nums[i] == 0. A zero jump length at index i only blocks you if i == max_reach (you can’t jump past it). If i < max_reach, you don’t even need to use index i — you can skip over it.

Checking i >= n as the success condition. Just let the loop complete normally. If you survive the entire loop without ever being stuck (i > max_reach), you’ve succeeded.

Confusing maximum jump with exact jump. nums[i] is the maximum jump, not a required jump. You can jump less. That’s why tracking max_reach = max(max_reach, i + nums[i]) is correct — we update with the farthest possible, knowing any intermediate index is also reachable.