Jump Game | Leetcode 55

Welcome to our definitive, multi-stage guide on Jump Game (Leetcode 55). This problem represents a perfect gateway into understanding the difference between the Dynamic Programming paradigm and the Greedy Algorithm paradigm.

Problem Statement

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

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

Example 1: nums = [2, 3, 1, 1, 4] => Output: true (Jump 1 step from index 0 to 1, then 3 steps to the last index).

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

Approach 1: Recursive Backtracking (Brute Force)

The absolute most naive way to solve this is to simply physically simulate every possible jump from the first index.

If we are standing at index i, its value nums[i] tells us how far we can jump. So we use a for loop to test jumping 1 step, 2 steps, 3 steps... all the way up to nums[i] steps. If any of those jumps eventually leads to the end of the array, we return true.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        def dfs(i):
            if i >= len(nums) - 1:
               return True
               
            furthest_jump = min(i + nums[i], len(nums) - 1)
            
            # Try every possible jump length from 1 to nums[i]
            for next_jump in range(i + 1, furthest_jump + 1):
                if dfs(next_jump):
                    return True
            
            return False
            
        return dfs(0)

Complexity Analysis

Approach 2: Top-Down Dynamic Programming (Memoization)

If you draw out the recursion tree for the brute force approach, you quickly realize we are asking "can we reach the end from index 3?" over and over again from different branching paths.

We can optimize this by maintaining a memo array of enum values (GOOD, BAD, UNKNOWN).

Once we successfully (or unsuccessfully) test an index, we permanently write it down so we never simulate it natively twice.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        memo = ["UNKNOWN"] * len(nums)
        memo[-1] = "GOOD"
        
        def dfs(i):
            if memo[i] != "UNKNOWN":
                return True if memo[i] == "GOOD" else False
                
            furthest_jump = min(i + nums[i], len(nums) - 1)
            for next_jump in range(i + 1, furthest_jump + 1):
                if dfs(next_jump):
                    memo[i] = "GOOD"
                    return True
                    
            memo[i] = "BAD"
            return False
            
        return dfs(0)

Complexity Analysis

Approach 3: Linear Greedy Algorithm (Optimal)

How do we do this efficiently? Instead of simulating every possible jump recursively natively, we can just linearly scan the array and keep a running total of the maximum index we can possibly reach. Let's call this variable maxReach (or work backwards using a goal post).

At each step i:

1. Check if i is greater than maxReach. If it is, that means we are physically standing on an index we could not possibly have reached. We immediately return false.
2. Otherwise, update maxReach to the maximum of its current value and i + nums[i].
3. If maxReach ever exceeds or equals the last index (nums.length - 1), we can return true.

graph LR
    A["nums = [2, 3, 1, 1, 4]"]
    
    subgraph Iteration
    B("[Idx 0] Val: 2 -> Reach: 2")
    C("[Idx 1] Val: 3 -> Reach: max(2, 1+3) = 4")
    D{"Reach=4 >= Last(4)? Return True!"}
    end
    
    A --> B
    B --> C
    C --> D
    
    style D fill:#4CAF50,stroke:#fff,stroke-width:2px,color:#fff

By greedily updating our maxReach, we completely bypass all branching DP logic.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # We can also work backwards from the goal elegantly!
        goal = len(nums) - 1
        
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal:
                goal = i
                
        return True if goal == 0 else False

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (55)