text
function canReach(index):
    if index == last_index:
        return true
    max_jump = nums[index]
    for jump from 1 to max_jump:
        if canReach(index + jump):
            return true
    return false

Why it fails: The time complexity of this approach is exponential, specifically $O(N^N)$ in the worst case (or $O(2^N)$ depending on jump sizes). For an array of length $10^4$ (as per constraints), the recursion tree grows excessively large, resulting in a Time Limit Exceeded (TLE) error. The algorithm repeatedly recalculates reachability for the same indices without memorizing the results.

Core Insight for Jump Game

The key intuition that transitions us from a naive simulation to an optimal greedy solution is the realization that we do not need to track how we get to an index, nor do we need to track every reachable index. We only need to track the maximum reachable index (let's call it maxReach) from the starting point.

If we can reach index i, and nums[i] allows us to jump k steps, then we can inherently reach every index between i and i + k. Therefore, the set of reachable indices is always a contiguous range starting from 0.

As we iterate through the array, we update maxReach based on the jump power at the current position. The invariant is simple: as long as the current index i is less than or equal to maxReach, we are on a valid path. If i ever exceeds maxReach, it means the current index is disconnected from the start, and the end is unreachable.

Visual Description: Imagine a "frontier" line moving across the array. Initially, the frontier is at index 0. As you visit each index up to the frontier, the value at that index may push the frontier further to the right. If your iteration catches up to the frontier and the frontier does not move forward (because the jump value is 0), you are stuck. If the frontier reaches or passes the last index, you succeed.

Execution Flow

Consider the input nums = [2, 3, 1, 1, 4]. Length is 5. Target index is 4.

1. Start: maxReach = 0.
2. i = 0:
   • Is 0 > maxReach (0)? No.
   • Update maxReach: max(0, 0 + 2) = 2.
   • maxReach is not $\ge 4$. Continue.
3. i = 1:
   • Is 1 > maxReach (2)? No.
   • Update maxReach: max(2, 1 + 3) = 4.
   • Check: maxReach (4) $\ge$ Target (4).
   • Return True.

Consider the input nums = [3, 2, 1, 0, 4]. Target index is 4.

1. Start: maxReach = 0.
2. i = 0: maxReach becomes 0 + 3 = 3.
3. i = 1: maxReach becomes max(3, 1 + 2) = 3.
4. i = 2: maxReach becomes max(3, 2 + 1) = 3.
5. i = 3: maxReach becomes max(3, 3 + 0) = 3.
6. i = 4:
   • Is 4 > maxReach (3)? Yes.
   • We cannot reach index 4.
   • Return False.

Proof of Correctness

The correctness relies on the "contiguous reachability" property. If we can reach index $X$, we can reach all indices $0 \dots X$.

• Base Case: We start at index 0, so we can reach index 0.
• Inductive Step: Assume we can reach all indices up to maxReach. For any valid i ($i \le maxReach$), the jump nums[i] allows us to reach i + nums[i]. Since we can reach i, we can naturally reach any point between i and i + nums[i]. By taking the maximum of all i + nums[i], we extend the contiguous range of reachable indices to the new maxReach.
• Conclusion: If the loop finishes or maxReach covers the last index, a path exists. If the iterator i surpasses maxReach, there is a gap in reachability that cannot be bridged.

Reference Implementation

C++ Solution for LeetCode 55

cpp
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; ++i) {
            // If the current index is beyond our maximum reach,
            // we cannot proceed further.
            if (i > maxReach) {
                return false;
            }
            
            // Update the furthest reachable index
            maxReach = max(maxReach, i + nums[i]);
            
            // Optimization: If we can already reach the end, return true
            if (maxReach >= n - 1) {
                return true;
            }
        }
        
        return true;
    }
};

Java Solution for LeetCode 55

java
class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            // If current index is not reachable, we are stuck
            if (i > maxReach) {
                return false;
            }
            
            // Update the maximum reach based on current position's jump power
            maxReach = Math.max(maxReach, i + nums[i]);
            
            // Early exit if we can reach the last index
            if (maxReach >= n - 1) {
                return true;
            }
        }
        
        return true;
    }
}

Python Solution for LeetCode 55

python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0
        n = len(nums)
        
        for i, jump in enumerate(nums):
            # If current index is beyond reachable range
            if i > max_reach:
                return false
            
            # Update the furthest point we can reach
            max_reach = max(max_reach, i + jump)
            
            # If we can reach the last index, return True immediately
            if max_reach >= n - 1:
                return True
                
        return True

Why does my code fail on [0]? A common mistake is incorrectly initializing loop bounds or exit conditions. If the array has a single element [0], you are already at the last index. The logic must handle this case; a loop from 0 to n-1 with the check if maxReach >= n-1 handles this correctly as 0 >= 0 is true.

Why is checking nums[i] == 0 not sufficient to return false? Seeing a 0 does not automatically mean failure. You might be able to jump over that zero from a previous index. The failure condition is strictly i > maxReach, not the value of nums[i] itself.