Jump Game: Multiple Solutions and Complexity Analysis

Introduction to the Jump Game

The Jump Game is a classic algorithmic problem that tests your ability to reason about array traversal, optimal substructure, and greedy decision-making. At its core, the problem asks: given an array of non-negative integers where each element represents your maximum jump distance from that position, can you determine whether you can reach the last index starting from the first?

This problem appears frequently in coding interviews at companies like Google, Amazon, and Facebook. It serves as an excellent lens for understanding how different algorithmic paradigms—backtracking, dynamic programming, and greedy algorithms—can be applied to the same problem, each with dramatically different performance characteristics.

Problem Statement

You are given an integer array nums of length n. The value at nums[i] represents the maximum number of steps you can jump forward from index i. You start at index 0. Return true if you can reach the last index (index n - 1), or false otherwise.

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. Its maximum jump is 0,
so you can never reach index 4.

Why This Problem Matters

Beyond interview preparation, the Jump Game embodies concepts that translate directly to real-world systems:

• Network routing: determining reachability between nodes given hop constraints
• Game development: platformer character movement with variable jump capabilities
• Resource allocation: assessing whether a sequence of operations can complete within constraints
• Algorithmic thinking: recognizing when greedy approaches are provably optimal

Most importantly, this problem teaches you to question your assumptions. The brute-force solution is exponential, but with clever reasoning, you can achieve linear time complexity.

Solution 1: Brute Force via Backtracking

The most intuitive approach mimics how a player might explore possibilities: at each position, try every valid jump amount and see if any path leads to the goal. This is a depth-first search over the implicit graph formed by array indices.

Approach

Write a recursive function that takes the current index. If the current index is the last index, return true. Otherwise, for each possible jump from 1 up to nums[currentIndex], recurse to the new index. If any recursive call succeeds, propagate true upward.

JavaScript Implementation

/**
 * Brute-force backtracking solution for Jump Game
 * Time Complexity: O(2^n) in the worst case
 * Space Complexity: O(n) for the recursion stack
 */
function canJumpBruteForce(nums) {
    function backtrack(index) {
        // Base case: reached or passed the last index
        if (index >= nums.length - 1) {
            return true;
        }
        
        // If current position has zero jump, we're stuck
        if (nums[index] === 0) {
            return false;
        }
        
        // Try every possible jump length from 1 to nums[index]
        const maxJump = nums[index];
        for (let jump = 1; jump <= maxJump; jump++) {
            const nextIndex = index + jump;
            if (backtrack(nextIndex)) {
                return true;
            }
        }
        
        // No path found from this position
        return false;
    }
    
    return backtrack(0);
}

// Example usage:
console.log(canJumpBruteForce([2, 3, 1, 1, 4])); // true
console.log(canJumpBruteForce([3, 2, 1, 0, 4])); // false

Python Implementation

def can_jump_brute_force(nums):
    def backtrack(index):
        # Base case: reached or passed the last index
        if index >= len(nums) - 1:
            return True
        
        # If stuck at a zero, no progress possible
        if nums[index] == 0:
            return False
        
        # Explore all possible jumps
        max_jump = nums[index]
        for jump in range(1, max_jump + 1):
            next_index = index + jump
            if backtrack(next_index):
                return True
        
        return False
    
    return backtrack(0)

# Example usage:
print(can_jump_brute_force([2, 3, 1, 1, 4]))  # True
print(can_jump_brute_force([3, 2, 1, 0, 4]))  # False

Complexity Analysis

• Time Complexity: O(2ⁿ) — at each position, you branch up to nums[i] ways. In the worst case (e.g., [2,2,2,...,2,0]), the recursion tree explodes exponentially.
• Space Complexity: O(n) — the recursion stack can grow as deep as the array length.

This solution works for small inputs but times out on arrays larger than about 20–30 elements. We clearly need optimization.

Solution 2: Dynamic Programming — Top-Down Memoization

The backtracking approach recomputes the same subproblems many times. For example, if indices 3 and 5 both lead to index 7, the reachability of index 7 is evaluated twice. We can cache results in a memoization table to avoid redundant work.

Approach

Create a memoization array memo initialized to null (unknown). When you compute whether an index can reach the end, store the boolean result. Before recursing, check the memo table first.

JavaScript Implementation

/**
 * Top-down DP with memoization
 * Time Complexity: O(n²) — each index computed once, each computation
 *   may scan up to nums[i] possibilities
 * Space Complexity: O(n) for memo array and recursion stack
 */
function canJumpMemo(nums) {
    const n = nums.length;
    const memo = new Array(n).fill(null);
    
    function dp(index) {
        // Base case: at or beyond the last index
        if (index >= n - 1) {
            return true;
        }
        
        // Check memoization cache
        if (memo[index] !== null) {
            return memo[index];
        }
        
        // Try each possible jump
        const maxJump = nums[index];
        for (let jump = 1; jump <= maxJump; jump++) {
            const nextIndex = index + jump;
            if (dp(nextIndex)) {
                memo[index] = true;
                return true;
            }
        }
        
        // Mark as unreachable from this index
        memo[index] = false;
        return false;
    }
    
    return dp(0);
}

// Example usage:
console.log(canJumpMemo([2, 3, 1, 1, 4])); // true
console.log(canJumpMemo([3, 2, 1, 0, 4])); // false

Python Implementation

def can_jump_memo(nums):
    n = len(nums)
    memo = [None] * n
    
    def dp(index):
        if index >= n - 1:
            return True
        
        if memo[index] is not None:
            return memo[index]
        
        max_jump = nums[index]
        for jump in range(1, max_jump + 1):
            next_index = index + jump
            if dp(next_index):
                memo[index] = True
                return True
        
        memo[index] = False
        return False
    
    return dp(0)

# Example usage:
print(can_jump_memo([2, 3, 1, 1, 4]))  # True
print(can_jump_memo([3, 2, 1, 0, 4]))  # False

Complexity Analysis

• Time Complexity: O(n²) — each of the n indices is evaluated exactly once. For each evaluation, we may iterate over up to nums[i] jump options, which in the worst case (e.g., [n, n-1, n-2, ..., 1]) sums to O(n²).
• Space Complexity: O(n) — the memoization array and recursion stack both use linear space.

This is a significant improvement over brute force and will handle arrays of hundreds of elements comfortably. But we can still do better.

Solution 3: Dynamic Programming — Bottom-Up

Instead of recursion, we can build the solution iteratively from the end of the array toward the beginning. This eliminates recursion overhead and makes the algorithm purely iterative.

Approach

Create a boolean array dp of length n. Set dp[n-1] = true (the last index is always reachable from itself). Then iterate from n-2 down to 0. For each index i, check if any reachable index within i+1 to i+nums[i] is marked true in dp. If so, dp[i] = true.

JavaScript Implementation

/**
 * Bottom-up dynamic programming
 * Time Complexity: O(n²) worst case, O(n) best case
 * Space Complexity: O(n)
 */
function canJumpBottomUp(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(false);
    
    // The last index is trivially reachable from itself
    dp[n - 1] = true;
    
    // Process from right to left
    for (let i = n - 2; i >= 0; i--) {
        const maxJump = nums[i];
        // Check if any position within our jump range is reachable
        for (let jump = 1; jump <= maxJump && i + jump < n; jump++) {
            if (dp[i + jump]) {
                dp[i] = true;
                break; // No need to check further
            }
        }
        // If no reachable position was found, dp[i] stays false
    }
    
    return dp[0];
}

// Example usage:
console.log(canJumpBottomUp([2, 3, 1, 1, 4])); // true
console.log(canJumpBottomUp([3, 2, 1, 0, 4])); // false

Python Implementation

def can_jump_bottom_up(nums):
    n = len(nums)
    dp = [False] * n
    dp[n - 1] = True  # Last index is always reachable from itself
    
    # Process from right to left
    for i in range(n - 2, -1, -1):
        max_jump = nums[i]
        # Check positions within jump range
        for jump in range(1, max_jump + 1):
            next_idx = i + jump
            if next_idx < n and dp[next_idx]:
                dp[i] = True
                break  # No need to check further
    
    return dp[0]

# Example usage:
print(can_jump_bottom_up([2, 3, 1, 1, 4]))  # True
print(can_jump_bottom_up([3, 2, 1, 0, 4]))  # False

Complexity Analysis

• Time Complexity: O(n²) in the worst case (dense array with large jump values), but often much faster in practice due to the break early exit.
• Space Complexity: O(n) for the DP table.

This bottom-up approach is cleaner and avoids recursion limits, making it suitable for very large inputs where recursion depth might be a concern. However, we still have room for a breakthrough optimization.

Solution 4: Greedy Algorithm (Optimal)

Here's where the problem reveals its elegance. We don't need to track reachability for every index. Instead, we can maintain a single variable: the farthest reachable index so far. If at any point the current index surpasses this reachable range, we know we're stuck.

Key Insight

As we iterate from left to right, we greedily update the maximum index we can reach. If at index i, the farthest we've ever been able to reach is i itself (meaning we can't go further), and nums[i] is 0, we return false. Otherwise, we extend our reach. This works because the greedy choice—always pushing the boundary as far as possible—is optimal: you never need to deliberately not extend your maximum reach.

JavaScript Implementation

/**
 * Greedy solution — optimal
 * Time Complexity: O(n) — single pass through the array
 * Space Complexity: O(1) — only a few variables
 */
function canJumpGreedy(nums) {
    let maxReach = 0;
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        // If current index is beyond the farthest we can reach
        if (i > maxReach) {
            return false;
        }
        
        // Update the farthest reachable index
        maxReach = Math.max(maxReach, i + nums[i]);
        
        // Early exit: if we can already reach the last index
        if (maxReach >= n - 1) {
            return true;
        }
    }
    
    // If we processed all indices without returning false,
    // check if we can reach the last index
    return maxReach >= n - 1;
}

// Example usage:
console.log(canJumpGreedy([2, 3, 1, 1, 4])); // true
console.log(canJumpGreedy([3, 2, 1, 0, 4])); // false

Python Implementation

def can_jump_greedy(nums):
    max_reach = 0
    n = len(nums)
    
    for i in range(n):
        # If current index is beyond our maximum reach
        if i > max_reach:
            return False
        
        # Greedily extend our reach
        max_reach = max(max_reach, i + nums[i])
        
        # Early termination if we can already reach the end
        if max_reach >= n - 1:
            return True
    
    return max_reach >= n - 1

# Example usage:
print(can_jump_greedy([2, 3, 1, 1, 4]))  # True
print(can_jump_greedy([3, 2, 1, 0, 4]))  # False

Complexity Analysis

• Time Complexity: O(n) — we scan the array exactly once, performing constant-time operations at each step.
• Space Complexity: O(1) — only two integer variables (maxReach and loop counter).

This is the solution interviewers hope to see. It's elegant, fast, and memory-efficient. The greedy insight—that you should always push your maximum reach as far as possible—is provably correct because any "conservative" strategy that doesn't extend the boundary can only hurt your chances of reaching the end.

Extension: Jump Game II — Minimum Jumps

A natural follow-up problem asks: what is the minimum number of jumps required to reach the last index? This is Jump Game II, and it introduces new algorithmic challenges. Let's explore solutions for this variation.

Problem Statement (Jump Game II)

Given the same input array, return the minimum number of jumps to reach the last index. You can assume you can always reach the last index.

Greedy BFS-like Solution (Optimal)

The key insight: group indices by "levels" (jump count). At each level, determine the farthest you can reach in the next jump. When the current level's range can touch the last index, you've found the answer.

JavaScript Implementation

/**
 * Jump Game II: Minimum number of jumps
 * Greedy BFS-like approach
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function minJumps(nums) {
    const n = nums.length;
    
    // Edge case: already at the end
    if (n <= 1) return 0;
    
    let jumps = 0;
    let currentEnd = 0;   // End of the current jump range
    let farthest = 0;     // Farthest we can reach in the next jump
    
    for (let i = 0; i < n - 1; i++) {
        // Update the farthest reachable index from within the current range
        farthest = Math.max(farthest, i + nums[i]);
        
        // If we've reached the end of the current jump's range
        if (i === currentEnd) {
            jumps++;
            currentEnd = farthest;
            
            // If the new range covers the last index, we're done
            if (currentEnd >= n - 1) {
                break;
            }
        }
    }
    
    return jumps;
}

// Example usage:
console.log(minJumps([2, 3, 1, 1, 4])); // 2 (jump to index 1, then to 4)
console.log(minJumps([2, 3, 0, 1, 4])); // 3

Python Implementation

def min_jumps(nums):
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(n - 1):
        # Extend the farthest reach within the current level
        farthest = max(farthest, i + nums[i])
        
        # When we hit the boundary of the current level
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            # If we can already reach the last index
            if current_end >= n - 1:
                break
    
    return jumps

# Example usage:
print(min_jumps([2, 3, 1, 1, 4]))  # 2
print(min_jumps([2, 3, 0, 1, 4]))  # 3

How It Works

Imagine partitioning the array into "layers" based on jump count:

• Jump 0: you're at index 0 (range: [0, 0])
• Jump 1: from index 0, you can reach up to index 0 + nums[0]
• Jump 2: from any index in the Jump-1 range, compute the farthest you can land

The variable currentEnd marks the boundary of the current jump level. When i hits currentEnd, you've exhausted the current level and must take another jump. The farthest variable continuously tracks the maximum boundary of the next level.

Complexity Analysis (Jump Game II)

• Time Complexity: O(n) — single pass through the array.
• Space Complexity: O(1) — only three variables.

Complexity Analysis Summary

Here's a side-by-side comparison of all approaches for Jump Game I:

Best Practices and Interview Tips

When Asked This Problem in an Interview

• Start simple: Verbally describe the brute-force approach first. This shows you understand the problem space.
• Identify inefficiencies: Point out overlapping subproblems and suggest memoization or DP.
• Pivot to greedy: Ask yourself: "Is there a way to track only the best possible outcome so far?" The greedy solution for Jump Game I emerges from observing that you always want to maximize reach.
• Prove correctness: For the greedy approach, articulate why it's optimal: "At each step, extending our maximum reach can never hurt us because we're not committing to a specific path, only expanding possibilities."

Common Pitfalls

• Off-by-one errors: The last index is n-1, not n. Reaching n-1 or any index beyond it counts as success.
• Zero values: A zero at an index before the last index creates a dead end. Handle this explicitly.
• Early return: In the greedy solution, return true as soon as maxReach >= n-1 to save iterations.
• Jump Game II assumption: The problem guarantees you can reach the end. If this guarantee is absent, add a reachability check first.

Edge Cases to Test

// Single element array
canJumpGreedy([0]);        // true (already at the end)

// Immediate reach
canJumpGreedy([5, 0, 0]);  // true

// Zero trap
canJumpGreedy([1, 0, 1]);  // false (stuck at index 1)

// Large jumps
canJumpGreedy([10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]); // true

// All ones
canJumpGreedy([1, 1, 1, 1, 1]); // true

Conclusion

The Jump Game problem suite is a masterclass in algorithmic optimization. Starting from an exponential backtracking approach, we progressively refined our solution through memoization, bottom-up dynamic programming, and finally arrived at an elegant O(n) greedy algorithm that uses constant space. The extension to Jump Game II demonstrates how greedy thinking can solve seemingly complex minimization problems with remarkable simplicity. When you encounter a problem involving sequential choices and optimal outcomes, always ask: can I track just the best possible state so far? More often than you might expect, the answer is yes—and the resulting code will be both beautiful and blazingly fast.