Problem Description

You are given an integer array nums where you start at the first index (position 0). Each element nums[i] represents the maximum number of steps you can jump forward from position i.

Your goal is to determine if you can reach the last index of the array by jumping.

For example:

• If you're at position i and nums[i] = 3, you can jump to position i+1, i+2, or i+3
• If nums[i] = 0, you cannot jump from that position

Return true if you can reach the last index, otherwise return false.

The solution uses a greedy approach by tracking the farthest position reachable (mx). As we iterate through the array:

1. If the current position i is beyond the farthest reachable position (mx < i), we cannot reach this position, so return false
2. Otherwise, update the farthest reachable position: mx = max(mx, i + nums[i])
3. If we complete the iteration without returning false, we can reach the last index

The algorithm works because it continuously updates the maximum reachable position. If at any point we encounter a position that cannot be reached (beyond our maximum reach), the last index is unreachable. Otherwise, we can always reach the last index.

Time complexity: O(n) where n is the length of the array
Space complexity: O(1) as we only use a single variable to track the maximum reach

Intuition

The key insight is to think about the problem in terms of "reachable zones" rather than trying every possible jump combination.

Imagine you're standing at the start of the array. From your current position, you can see how far you could potentially reach - this creates a "reachable zone". As you move through positions within this zone, each position might extend your reachable zone even further.

The critical observation is: if you can reach a position, you can reach all positions before it. This means we don't need to track every possible path; we only need to track the farthest position we can reach.

Think of it like this: as you walk through the array from left to right, at each position you ask:

1. "Can I even reach this position?" (Is i <= mx?)
2. "If yes, how far can I extend my reach from here?" (Update mx = max(mx, i + nums[i]))

If at any point you encounter a position i that is beyond your maximum reach (i > mx), you've found a gap you cannot cross, making the last index unreachable.

Why does this greedy approach work? Because we're always maintaining the best possible scenario - the farthest we could possibly reach. If even in this best-case scenario we cannot reach a certain position, then there's no way to reach the last index.

This transforms the problem from "find a valid path to the end" to "continuously expand your reachable boundary and check if the end falls within it".

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

The solution implements a greedy algorithm that tracks the maximum reachable position as we iterate through the array.

Algorithm Steps:

1. Initialize the maximum reach: Start with mx = 0, representing that initially we can only reach the starting position.

2. Iterate through the array: For each position i and its value x (using enumerate(nums)):

   a. Check if current position is reachable: If mx < i, it means our maximum reach is less than the current position, so position i cannot be reached. Return False immediately.

   b. Update maximum reach: If we can reach position i, calculate how far we can jump from here: i + x. Update mx to be the maximum of the current mx and this new potential reach: mx = max(mx, i + x).

3. Return result: If we successfully iterate through the entire array without returning False, it means all positions up to the last index are reachable. Return True.

Why this works:

• The variable mx always maintains the farthest index we can possibly reach from all positions we've visited so far
• By checking mx < i before processing each position, we ensure we only consider jumps from reachable positions
• The greedy choice of always tracking the maximum reach is optimal because having a larger reachable zone never hurts - it only gives us more options

Example walkthrough:

For nums = [2, 3, 1, 1, 4]:

• Position 0: mx = max(0, 0+2) = 2
• Position 1: mx = max(2, 1+3) = 4 (can reach the end!)
• Position 2: mx = max(4, 2+1) = 4
• Position 3: mx = max(4, 3+1) = 4
• Position 4: Already reachable, return True

For nums = [3, 2, 1, 0, 4]:

• Position 0: mx = max(0, 0+3) = 3
• Position 1: mx = max(3, 1+2) = 3
• Position 2: mx = max(3, 2+1) = 3
• Position 3: mx = max(3, 3+0) = 3
• Position 4: mx = 3 < 4, return False

The time complexity is O(n) as we visit each element once, and space complexity is O(1) as we only use a single variable mx.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: nums = [2, 1, 0, 3]

We want to determine if we can reach the last index (position 3).

Initial State:

• Start at position 0
• mx = 0 (initially we can only reach the starting position)

Step-by-step execution:

Position 0 (value = 2):

• Check: Is mx < 0? No, 0 < 0 is false, so position 0 is reachable ✓
• From position 0, we can jump up to 2 steps forward
• Update mx = max(0, 0 + 2) = 2
• This means we can now reach positions 1 and 2

Position 1 (value = 1):

• Check: Is mx < 1? No, 2 < 1 is false, so position 1 is reachable ✓
• From position 1, we can jump up to 1 step forward
• Update mx = max(2, 1 + 1) = 2
• Maximum reach stays at position 2

Position 2 (value = 0):

• Check: Is mx < 2? No, 2 < 2 is false, so position 2 is reachable ✓
• From position 2, we can jump 0 steps (stuck here!)
• Update mx = max(2, 2 + 0) = 2
• Maximum reach remains at position 2

Position 3 (value = 3):

• Check: Is mx < 3? Yes, 2 < 3 is true!
• Position 3 is beyond our maximum reach
• We cannot reach position 3, so return False

Visualization of reachable zones:

Position: [0] [1] [2] [3]
Values:    2   1   0   3
          ╰─────╯       From position 0, reach positions 1-2
              ╰─╯       From position 1, reach position 2
                  X     From position 2, stuck (can't jump)
                        Position 3 is unreachable!

The algorithm correctly identifies that we cannot reach the last index because position 2 has a value of 0, creating an impassable barrier. Our maximum reach gets stuck at position 2, and we cannot jump to position 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums. The algorithm iterates through the array exactly once using a single for loop. Each iteration performs constant time operations: comparing mx with i, returning a boolean value, and updating mx using the max function. Since we visit each element at most once, the overall time complexity is linear.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space. It maintains a single integer variable mx to track the maximum reachable index, and uses the loop variables i and x which don't depend on the input size. No additional data structures like arrays, lists, or recursive call stacks are used, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Early Termination When Maximum Reach Exceeds Array Length

A common mistake is trying to optimize by adding an early termination condition when max_reachable >= len(nums) - 1, thinking we can immediately return True once we know we can reach the last index:

# Incorrect optimization attempt
def canJump(self, nums: List[int]) -> bool:
    max_reachable = 0
    for current_pos, jump_length in enumerate(nums):
        if max_reachable < current_pos:
            return False
        max_reachable = max(max_reachable, current_pos + jump_length)
        # Pitfall: unnecessary early return
        if max_reachable >= len(nums) - 1:
            return True
    return True

Why it's a pitfall: While this optimization seems logical and doesn't break correctness, it adds unnecessary complexity and an extra comparison in each iteration. The original solution is already O(n) and will naturally return True at the end if the last index is reachable.

2. Misunderstanding the Initial Maximum Reach

Some might initialize max_reachable to nums[0] instead of 0:

# Incorrect initialization
def canJump(self, nums: List[int]) -> bool:
    if not nums:
        return False
    max_reachable = nums[0]  # Wrong!
    for i in range(1, len(nums)):
        if max_reachable < i:
            return False
        max_reachable = max(max_reachable, i + nums[i])
    return True

Why it's a pitfall: This creates inconsistency in the logic. Starting with max_reachable = 0 represents that we begin at index 0 and can reach at least that position. The first iteration will then properly update it to 0 + nums[0]. Setting it to nums[0] initially skips the logical step of processing position 0.

3. Off-by-One Error in Reachability Check

A subtle mistake is using <= instead of < when checking if a position is reachable:

# Incorrect comparison
def canJump(self, nums: List[int]) -> bool:
    max_reachable = 0
    for current_pos, jump_length in enumerate(nums):
        if max_reachable <= current_pos:  # Wrong! Should be <
            return False
        max_reachable = max(max_reachable, current_pos + jump_length)
    return True

Why it's a pitfall: Using max_reachable <= current_pos would incorrectly mark a position as unreachable when max_reachable == current_pos, which actually means we can exactly reach that position. This would cause the algorithm to fail on valid inputs like [0] or [2,0,0].

4. Not Handling Edge Cases Properly

Forgetting to consider special cases like single-element arrays:

# Missing edge case handling
def canJump(self, nums: List[int]) -> bool:
    # Might forget that a single element array needs no jumps
    if len(nums) == 1:
        return True  # Easy to forget this case
  
    max_reachable = 0
    for current_pos, jump_length in enumerate(nums):
        if max_reachable < current_pos:
            return False
        max_reachable = max(max_reachable, current_pos + jump_length)
    return True

Solution: The original algorithm naturally handles this case without special checking. When nums = [0], the loop runs once with current_pos = 0 and max_reachable = 0, so the condition max_reachable < current_pos is false (0 < 0 is false), and it returns True.

Best Practice Solution

The original solution avoids all these pitfalls by:

• Starting with max_reachable = 0 (we start at position 0)
• Using the correct comparison max_reachable < current_pos
• Letting the algorithm naturally handle edge cases
• Avoiding premature optimizations that don't improve complexity