Jump Game — DP Reachability and the Greedy Insight

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.

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

Example 1:

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

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 is 0.
             You cannot move further.

Example 3:

Input:  nums = [0]
Output: true
Explanation: Already at the last index.

Why This Problem Matters#

Jump Game (LeetCode 55) is an important bridge problem that demonstrates when greedy is provably optimal over dynamic programming. The DP approach works and is instructive, but is O(n^2). The greedy insight — tracking the furthest reachable index in one pass — achieves O(n) O(1) and is the expected solution at Amazon and Google.

This problem also teaches a valuable interview skill: always ask yourself "is DP necessary, or can I do better with a simpler pass?" Many candidates reflexively reach for DP when greedy suffices. Recognizing the greedy shortcut here demonstrates algorithmic maturity.

Jump Game pairs naturally with Jump Game II (LC 45), which extends the question from "can you reach?" to "what is the minimum number of jumps?" Understanding both problems reveals how reachability and optimization share the same greedy structure.

The Core Insight#

Greedy insight: At any position i, if i is reachable, then all positions i+1, i+2, ..., i+nums[i] are also reachable. As you scan left to right, maintain the maximum index reachable so far (max_reach). If at any point your current position exceeds max_reach, you are stuck — the last index is unreachable.

max_reach = max(max_reach, i + nums[i]) for each position i <= max_reach.

If max_reach >= n - 1 at any point, return true. If the loop ends with max_reach >= n - 1, return true. If the current position i > max_reach at any point, return false.

Why greedy is correct: We always extend max_reach to the farthest possible position. Since we can jump any number of steps up to nums[i], we never benefit from jumping less than the maximum to a position we could already reach. The greedy choice is locally and globally optimal.

DP perspective: Define dp[i] = True if index i is reachable. Then dp[i] = any(dp[j] for j in range(max(0, i - nums[j]), i)). This is O(n^2). The greedy version is equivalent but avoids the inner loop by maintaining a single max_reach variable.

Building the DP Solution#

Step 1 — Naive DP (O(n^2))#

# Python — naive DP, O(n^2) — illustrative
def canJump(nums):
    n = len(nums)
    reachable = [False] * n
    reachable[0] = True
    for i in range(1, n):
        for j in range(i):
            if reachable[j] and j + nums[j] >= i:
                reachable[i] = True
                break
    return reachable[n - 1]

// JavaScript — naive DP, O(n^2)
function canJump(nums) {
    const n = nums.length;
    const reachable = new Array(n).fill(false);
    reachable[0] = true;
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (reachable[j] && j + nums[j] >= i) {
                reachable[i] = true;
                break;
            }
        }
    }
    return reachable[n - 1];
}

Step 2 — Top-Down Memoization (O(n^2) time, O(n) space)#

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def canJump(self, nums: list[int]) -> bool:
        n = len(nums)
 
        @lru_cache(maxsize=None)
        def can_reach(i: int) -> bool:
            if i == 0:
                return True
            return any(can_reach(j) and j + nums[j] >= i for j in range(i))
 
        return can_reach(n - 1)

This is still O(n^2) in the worst case even with memoization, because each position checks all previous positions.

Step 3 — Greedy One-Pass (O(n) time, O(1) space)#

# Python — greedy, O(n) time, O(1) space
class Solution:
    def canJump(self, nums: list[int]) -> bool:
        max_reach = 0
        for i in range(len(nums)):
            if i > max_reach:
                return False
            max_reach = max(max_reach, i + nums[i])
        return True

// JavaScript — greedy, O(n) time, O(1) space
var canJump = function(nums) {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
};

Optimized Solution#

The greedy one-pass solution is the optimized version. For extra clarity, with an early exit when the last index becomes reachable:

# Python — greedy with early exit
class Solution:
    def canJump(self, nums: list[int]) -> bool:
        max_reach = 0
        n = len(nums)
        for i in range(n):
            if i > max_reach:
                return False
            max_reach = max(max_reach, i + nums[i])
            if max_reach >= n - 1:
                return True
        return True

// JavaScript — greedy with early exit
var canJump = function(nums) {
    let maxReach = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= n - 1) return true;
    }
    return true;
};

Visual Dry Run#

Input: nums = [2, 3, 1, 1, 4], n = 5

max_reach = 8 >= 4 (last index). Return true.

Input: nums = [3, 2, 1, 0, 4], n = 5

Complexity Analysis#

Common Mistakes#

1. Checking if max_reach < n - 1 at the end instead of checking i > max_reach during the loop. Without the mid-loop check, you will scan past stuck positions and get wrong results. Always short-circuit when i > max_reach.

2. Starting max_reach at nums[0] instead of 0. Initialize max_reach = 0 and update it inside the loop. Starting at nums[0] skips the check at index 0 and can cause off-by-one issues.

3. Updating max_reach using i + 1 + nums[i] (adding 1 unnecessarily). The farthest reachable index from position i is i + nums[i]. No off-by-one adjustment needed.

4. Not handling nums = [0] (single element). The loop runs once with i = 0. max_reach = 0 + 0 = 0. After the loop, return true (already at last index). Confirm this handles correctly.

5. Thinking you need to actually jump optimally. You are only checking reachability. You do not need to simulate actual jumps — just maintain the frontier of reachable positions.

6. Using a DP array when greedy suffices. The reachable[] array approach works but uses O(n) space and O(n^2) time. Always upgrade to the greedy one-liner once you understand the DP first.

Interview Tips#

Present the DP first, then upgrade. Say: "I can define dp[i] as whether index i is reachable. dp[0] = true. For each i, dp[i] = true if any dp[j] with j + nums[j] >= i is true. This is O(n^2)." Then: "But notice I don't need the full dp array. I just need the maximum reachable index — tracking one variable is sufficient."

Prove the greedy is correct in one sentence. "The greedy is correct because we always track the farthest possible reach. At each step, extending as far as possible is never worse than stopping short."

Contrast with Jump Game II. "Jump Game asks if the last index is reachable. Jump Game II asks for the minimum jumps — same greedy idea but counting jump boundaries instead of just checking reachability."

Handle the edge case explicitly. "A single-element array means we start at the last index — immediately return true."

Follow-up Questions#

Q: What if you want the minimum number of jumps to reach the last index? That is Jump Game II (LC 45). Use the greedy boundary-extension approach: track curr_end, farthest, and jumps. Increment jumps when you reach curr_end.

Q: What if some positions are blocked (value = 0 means you must stay)? Value 0 means you cannot move from that position. The algorithm handles this naturally — max_reach does not extend from a position with nums[i] = 0 (unless you were already further).

Q: What if you can jump backwards? With bidirectional jumps, use BFS from index 0 and check reachability to the last index. The greedy forward-scan no longer suffices.

Q: What if you need to find all positions that can reach the last index? Scan from right to left, maintaining a target. Initially target = n - 1. A position i can reach target if i + nums[i] >= target. If so, update target = i. After the scan, target should be 0 if all positions from 0 can transitively reach the last index.

Q: What if you start from any position and want to reach any target? Generalize with BFS from all start positions simultaneously (multi-source BFS).

Key Takeaways#

• Jump Game is a reachability problem solvable with DP (O(n^2)) or greedy (O(n) O(1)). Always upgrade to greedy in interviews.
• The greedy insight: maintain max_reach = max(max_reach, i + nums[i]). If i > max_reach at any position, the last index is unreachable.
• The DP framing (dp[i] = reachable) collapses to a single variable (max_reach) because we only care about the frontier, not the full reachability table.
• Greedy is provably correct here: extending to the farthest reachable position at each step is never worse than stopping short.
• Jump Game (reachability) and Jump Game II (minimum jumps) share the same greedy framework — master both together.
• Always check i > max_reach inside the loop (not just at the end) to correctly handle zero-valued elements that create dead zones.