Jump Game: Why Greedy Beats DP (Proof and Complexity Comparison)

Jump Game is the perfect example of when greedy beats DP. The DP solution works but is O(n²). The greedy solution is O(n) and equally correct.

Understanding why greedy works here—and when to choose it over DP—is crucial for interviews.

TL;DR

DP Solution: O(n²) time, O(n) space
Greedy Solution: O(n) time, O(1) space

Why greedy works: If you can't reach position i with maximum possible reach, you can never reach it.

When to use greedy: Reachability problems where tracking maximum state suffices.

The Problem

LeetCode #55: Jump Game

Given an array where each element represents max jump length, determine if you can reach the last index.

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

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3, which has 0 jump length.

The DP Solution (O(n²))

def canJump(nums):
    n = len(nums)
    dp = [False] * n
    dp[0] = True  # Can reach start
    
    for i in range(n):
        if not dp[i]:
            continue
        
        # Try all jumps from position i
        for j in range(1, nums[i] + 1):
            if i + j < n:
                dp[i + j] = True
    
    return dp[n - 1]

Time: O(n²) - for each position, try all jumps
Space: O(n) - DP array

The Greedy Solution (O(n))

def canJump(nums):
    max_reach = 0
    
    for i in range(len(nums)):
        # Can't reach current position
        if i > max_reach:
            return False
        
        # Update maximum reachable position
        max_reach = max(max_reach, i + nums[i])
        
        # Early exit if we can reach the end
        if max_reach >= len(nums) - 1:
            return True
    
    return True

Time: O(n) - single pass
Space: O(1) - only track max_reach

Why Greedy Works: Tracking Maximum Reach

The Key Insight

Observation: If you can't reach position i with the best possible state (maximum reach from 0..i-1), you can never reach it.

Proof:

1. Let max_reach = farthest position reachable from indices 0..i-1
2. If i > max_reach:
   • Position i is beyond our reach
   • No future position can help (they're all beyond i)
   • Therefore, position i is unreachable ✓
3. If i ≤ max_reach:
   • Position i is reachable
   • Update max_reach = max(max_reach, i + nums[i])
   • Continue checking

Conclusion: Tracking maximum reach in one pass is sufficient.

Visual Example

Array: [2, 3, 1, 1, 4]

i=0: nums[0]=2, max_reach=max(0, 0+2)=2
  Can reach: 0, 1, 2

i=1: nums[1]=3, max_reach=max(2, 1+3)=4
  Can reach: 0, 1, 2, 3, 4

i=2: max_reach=4 ≥ 4 (last index)
  Early exit: True ✓

Proof of Correctness

Proof by Induction

Base case (n=1):

• Array of size 1: already at end ✓

Inductive hypothesis:

• Assume greedy correctly determines reachability for arrays of size n-1

Inductive step (size n):

• At position i:
  • If i > max_reach: unreachable (no future position can help)
  • If i ≤ max_reach: reachable, update max_reach
• Remaining problem: can we reach n-1 from positions i+1..n-1?
• This is a problem of size < n
• By inductive hypothesis, greedy works ✓

Conclusion: Greedy is correct for all n ✓

Complexity Comparison

Example: Array of size 1000

• Greedy: 1,000 operations
• DP: ~500,000 operations (500× slower)
• Backtracking: 2^1000 operations (impractical)

When to Use Each

Use Greedy When:

• ✅ Reachability problems
• ✅ Tracking maximum/minimum state suffices
• ✅ Don't need to count paths
• ✅ Want O(n) time, O(1) space

Use DP When:

• ❌ Need to count number of ways
• ❌ Need minimum steps (use Jump Game II)
• ❌ Complex state dependencies

Related Problems

Jump Game (#55): Can you reach end? → Greedy ✓
Jump Game II (#45): Minimum jumps? → Greedy with lookahead ✓
Jump Game III (#1306): Bidirectional jumps? → BFS or greedy ✓
Jump Game IV (#1345): With teleportation? → BFS (greedy doesn't work)

Conclusion

For Jump Game, greedy beats DP in every way: faster, simpler, less space.

Key insight: If unreachable with maximum possible reach, impossible.

For more on greedy state tracking, see Greedy State Tracking and the complete greedy guide.