Problem Statement #

Given an array of non-negative integers, you start at the first index of the array. Each element in the array represents your maximum jump length from that position. Your task is to determine whether you can reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Problem Analysis #

The key insight for this problem lies in understanding what “maximum jump length” means. At any position i, you can jump anywhere from 1 to nums[i] steps forward. This flexibility opens up multiple solution approaches, each with different trade-offs in terms of time complexity, space complexity, and code clarity.

The challenge becomes determining whether any combination of valid jumps from the starting position can reach the final index. This is essentially a reachability problem that can be solved through various algorithmic paradigms.

Solution Approaches #

Approach 1: Backtracking with Memoization (Top-Down Dynamic Programming) #

The backtracking approach explores all possible jump combinations recursively. At each position, we try every valid jump distance (from 1 to nums[i]) and recursively check if any of these jumps eventually leads to the last index.

How it works:

1. Start at index 0 and try all possible jump distances
2. For each jump, recursively check if that position can reach the end
3. Use memoization to cache results and avoid redundant calculations
4. If any path reaches the end, return true; otherwise, return false

Time Complexity: O(n²) - In the worst case, we visit each index and try jumps to all subsequent indices

Space Complexity: O(n) - For the recursion stack and cache array

var canJump = function(nums, index = 0, cache = []) {
    // Check if we've already computed the result for this index
    if (cache[index] !== undefined) {
        return cache[index];
    }
    
    // Base case: we've reached the last index
    if (index === nums.length - 1) {
        return true;
    }
    
    // Base case: we've jumped beyond the array (shouldn't happen with valid inputs)
    if (index >= nums.length) {
        return false;
    }
    
    // Try all possible jump distances from current position
    for (let i = 1; i <= nums[index]; i++) {
        const nextIndex = index + i;
        
        // Recursively check if this jump leads to a solution
        cache[nextIndex] = canJump(nums, nextIndex, cache);
        
        if (cache[nextIndex]) {
            return true; // Found a valid path to the end
        }
    }
    
    // No valid path found from this index
    cache[index] = false;
    return false;
};

Advantages:

• Intuitive approach that directly models the problem
• Memoization prevents redundant calculations
• Easy to modify for variations (e.g., counting paths, finding minimum jumps)

Disadvantages:

• Recursive calls consume stack space
• Not the most efficient solution for this specific problem
• May hit stack overflow on very large inputs

Approach 2: Greedy Algorithm (Optimal Solution) #

The greedy approach provides the most efficient solution by working backwards from the target. This solution leverages a crucial observation: if we can reach position j from position i, and position j can reach the end, then position i can also reach the end.

Key Insight:

Instead of asking “Can I reach the end from here?”, we ask “What’s the leftmost position that can reach my current target?” By iteratively moving our target leftward, we eventually determine if the starting position can reach the original target (the last index).

How it works:

1. Start with the last index as our target
2. Iterate backwards through the array
3. For each position, check if it can jump to the current target
4. If yes, update the target to this position
5. After checking all positions, if the target is at index 0, we can reach the end

Time Complexity: O(n) - Single pass through the array

Space Complexity: O(1) - Only using a constant amount of extra space

var canJump = function(nums) {
    // Start with the last index as our target
    let target = nums.length - 1;
    
    // Iterate backwards from the second-to-last element
    for (let i = nums.length - 2; i >= 0; i--) {
        // Calculate distance from current position to target
        const distance = target - i;
        
        // Check if we can reach the target from current position
        // If nums[i] >= distance, we can jump to or past the target
        if (nums[i] >= distance) {
            // Update target to current position
            // Now we just need to reach position i
            target = i;
        }
    }
    
    // If target has moved back to index 0, there's a valid path
    return target === 0;
};

Why this works:

The greedy choice is optimal because of the flexibility in jump distances. When we find a position that can reach our target, we know it can also reach any position between itself and the target. Therefore, we can safely make it our new target without missing any potential solutions.

Advantages:

• Optimal time complexity: O(n)
• Minimal space usage: O(1)
• No recursion or stack overflow concerns
• Clean and elegant code

Disadvantages:

• Less intuitive than the backtracking approach
• Requires understanding the key insight about working backwards

Alternative Greedy Approach: Forward Iteration #

There’s also a forward-moving greedy approach where we track the farthest position we can reach:

var canJump = function(nums) {
    let maxReach = 0;
    
    for (let i = 0; i < nums.length; i++) {
        // If current position is unreachable, return false
        if (i > maxReach) {
            return false;
        }
        
        // Update the farthest position we can reach
        maxReach = Math.max(maxReach, i + nums[i]);
        
        // If we can reach or pass the last index, return true
        if (maxReach >= nums.length - 1) {
            return true;
        }
    }
    
    return true;
};

This approach is equally efficient and some find it more intuitive.

Comparison and Recommendations #

When to use each approach:

• Backtracking with memoization: Use when learning the problem or when you need to extend the solution to count all paths, find the minimum number of jumps, or handle more complex constraints.

• Greedy algorithm (either direction): Use in production code or coding interviews where optimal performance is required. Choose the backward or forward variant based on which feels more intuitive to you.

Key Takeaways #

1. Problem structure matters: The “up to maximum jump” constraint makes greedy algorithms viable. If jumps were fixed distances or had other restrictions, dynamic programming might be necessary.

2. Working backwards can simplify problems: The backward greedy approach transforms a complex reachability problem into a simple iterative check.

3. Memoization adds value: Even though the greedy solution is optimal, understanding the memoized recursive approach helps with similar problems where greedy doesn’t apply.

4. Trade-offs exist: More intuitive solutions (backtracking) may be easier to understand and modify, while optimal solutions (greedy) require deeper insight but offer better performance.

Practice Extensions #

To deepen your understanding, consider these variations:

1. Jump Game II: Find the minimum number of jumps needed to reach the end
2. Jump Game III: Given an array where you can jump forward or backward by the value at each index, determine if you can reach any index with value 0
3. Jump Game IV: Given an array where you can jump to any index with the same value, find minimum jumps to reach the end

Each variation requires adapting these core techniques to new constraints, building your algorithmic problem-solving skills.