Jump Game — Greedy Max Reach O(n) Explained (The Definitive Guide) [Amazon, Google, Meta]

Problem Statement

You are given an integer array nums. You are initially positioned at the 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.

Examples:

Example 1 — reachable:
Input:  nums = [2, 3, 1, 1, 4]
Output: true
Reason: Jump 1 step from index 0 to 1, then 3 steps to the last index.
        (Or jump 2 steps from 0 to 2, then 1 step to 3, then 1 to 4.)

Example 2 — not reachable:
Input:  nums = [3, 2, 1, 0, 4]
Output: false
Reason: No matter how you jump, you always land on index 3 which has value 0.
        From there you cannot move forward at all.

Example 3 — single element:
Input:  nums = [0]
Output: true
Reason: You are already at the last index — no jump needed.

Constraints: 1 <= nums.length <= 10^4, 0 <= nums[i] <= 10^5

• Why This Problem Matters
• Two Approaches
• Approach 1 — Dynamic Programming: O(n²) Time, O(n) Space
• Approach 2 — Greedy: O(n) Time, O(1) Space
• The Greedy Insight — Why This Works
• Visual Dry Run
• Trace 1 — [2, 3, 1, 1, 4] → Expected: true
• Trace 2 — [3, 2, 1, 0, 4] → Expected: false
• Common Mistakes
• Mistake 1 — Terminating too early at a zero
• Mistake 2 — DP with memoization (over-engineering)
• Mistake 3 — Wrong loop condition (off-by-one)
• Mistake 4 — Not updating max_reach before the stuck check
• Mistake 5 — Confusing "max jump" with "exact jump"
• Solutions
• Python — DP Approach (O(n²) time, O(n) space)
• JavaScript — DP Approach (O(n²) time, O(n) space)
• Python — Greedy Approach (O(n) time, O(1) space)
• JavaScript — Greedy Approach (O(n) time, O(1) space)
• Complexity Analysis
• Follow-up Questions
• Jump Game II — LeetCode 45 (Minimum Jumps)
• Jump Game III — LeetCode 1306 (Reach Zero)
• Jump Game VI — LeetCode 1696 (Maximum Score)
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 55 is a staple on every serious FAANG prep list — Blind 75, NeetCode 150, and Grind 169 all include it — and it earns its place for a reason that goes beyond the algorithm itself.

It tests whether you know when to stop thinking in DP.

Most engineers, when they see "can you reach the end?", immediately reach for a boolean DP array: dp[i] = can I reach index i?. That works. It is O(n²) time, O(n) space, and perfectly correct. But the moment you submit it in a FAANG interview, a good interviewer follows up: "Can you do better?" The correct answer is yes — O(n) time and O(1) space — and the path there requires a conceptual insight that pure pattern-matching will not give you.

The insight: you do not need to know whether every individual index is reachable. You only need to know the furthest index your current frontier can touch. If that frontier has not yet reached position i by the time you visit it, you are stuck. That compression from tracking all reachable positions down to a single number is the hallmark of a greedy solution — and it is exactly what FAANG interviewers are probing for.

Interview frequency: Jump Game or a direct variant appears in roughly 1 in 4 array/greedy rounds at Amazon and Google, based on community reports on LeetCode Discuss and Blind. In September 2024, a candidate received the exact problem in an Amazon SDE-I virtual interview coding round. Google interviewers frequently use it as a warm-up to test algorithmic reasoning before pivoting to Jump Game II (minimum jumps) or a custom variant.

The difficulty rating of "Medium" is justified not by implementation complexity — the greedy solution is six lines — but by the mental leap required to see why greedy is correct and DP is unnecessary.

Two Approaches

Approach 1 — Dynamic Programming: O(n²) Time, O(n) Space

The DP formulation is natural and easy to justify:

dp[i] = true if index i is reachable from index 0

Base case: dp[0] = true (we start at index 0).

Transition: For each index i, it is reachable if there exists some previous index j < i such that dp[j] = true AND j + nums[j] >= i. Formally:

dp[i] = any(dp[j] and j + nums[j] >= i  for j in range(i))

Answer: dp[n-1]

This requires an outer loop over all indices and an inner loop over all previous positions — hence O(n²) in the worst case. Space is O(n) for the DP array.

The DP approach is correct and will pass the LeetCode test suite, but:

• Python often times out on worst-case inputs (n ~ 10^4) because the constant factor is high.
• It is unnecessarily detailed — we store reachability information for every single index, when we only ever query the last one.
• Interviewers will push you off it immediately.

Approach 2 — Greedy: O(n) Time, O(1) Space

Instead of tracking a boolean for every index, track a single integer: max_reach — the farthest index we can currently reach from any position we have visited.

max_reach = 0   # initially, only index 0 is reachable

for i from 0 to n-1:
    if i > max_reach:
        return false       # we can't even get to index i
    max_reach = max(max_reach, i + nums[i])

return true

One pass. Two lines of logic. No auxiliary array.

The Greedy Insight — Why This Works

The key question when validating a greedy algorithm is: "Is it safe to discard information?"

In DP, we preserve whether every individual index is reachable because we fear that a later index might need to jump back and check an earlier position. But notice what the transition actually says: "index i is reachable if any j before it can reach it." We never look ahead — we only look back.

This means the only thing that matters about the set of reachable positions {0, 1, ..., k} is its rightmost boundary k = max_reach. Why? Because the set of reachable positions is always a contiguous prefix starting at 0.

Here is the proof by induction:

• At step 0, the reachable set is {0} — a contiguous prefix ending at 0.
• Assume after processing index i, all positions 0..max_reach are reachable. When we visit i+1, if i+1 <= max_reach, it is reachable and max_reach potentially grows. The reachable set remains a contiguous prefix.
• If at any point i > max_reach, index i cannot be in the prefix — we are stuck.

The reachable set is always an interval, never a scattered collection of positions. Once you see that, the DP array collapses to a single integer: the right endpoint of that interval.

This is the core pattern that shows up in many "coverage" problems: whenever reachable positions form a contiguous window, tracking the window boundary is sufficient, and DP becomes overkill.

The one-line rule: At each index i, update max_reach = max(max_reach, i + nums[i]). If i > max_reach at any point, return false. After the loop, return true.

Visual Dry Run

Trace 1 — [2, 3, 1, 1, 4] → Expected: true

Loop completes without i > max_reach ever being true. Return true.

Notice at index 1, max_reach jumps to 4 — we can already see the finish line from index 1. The remaining iterations just confirm nothing breaks the frontier.

Trace 2 — [3, 2, 1, 0, 4] → Expected: false

At index 4, i (4) > max_reach (3). Return false.

The trap here is the zero at index 3. Every path from the left eventually lands on index 3, and from there no forward progress is possible. The max_reach gets frozen at 3 because 3 + 0 = 3. When we try to visit index 4, the frontier has not grown far enough.

Common Mistakes

Mistake 1 — Terminating too early at a zero

A frequent wrong approach: "If I see a zero, immediately return false." This fails on [1, 0, 1] — you can jump over the zero entirely from index 0. Zeros are only fatal if your max_reach cannot bridge them.

Mistake 2 — DP with memoization (over-engineering)

Writing a top-down recursive solution with a memo dict or @lru_cache works but is O(n²) in the worst case and O(n) space. It will often hit Python's default recursion limit on large inputs (you need sys.setrecursionlimit). More importantly, it signals to the interviewer that you have not found the greedy insight. Always pivot to greedy after stating the DP solution.

Mistake 3 — Wrong loop condition (off-by-one)

Using for i in range(n-1) instead of range(n) causes you to skip the last index check. Using for i in range(1, n) with max_reach initialized to nums[0] is an equivalent formulation but only works if n >= 1 — always handle the single-element edge case (n == 1 is always true).

Mistake 4 — Not updating max_reach before the stuck check

Some implementations write the check before the update on the same iteration:

# Wrong order — misses the case where i == max_reach but nums[i] > 0
for i in range(n):
    if i >= max_reach and nums[i] == 0:   # overly restrictive, wrong
        return False
    max_reach = max(max_reach, i + nums[i])

The correct pattern is: check i > max_reach first, then unconditionally update max_reach.

Mistake 5 — Confusing "max jump" with "exact jump"

The problem says nums[i] is the maximum jump, not the required jump. You can jump fewer steps. This is why greedy works: from any reachable index i, you can reach everything from i to i + nums[i]. The interval logic holds precisely because of this.

Solutions

Python — DP Approach (O(n²) time, O(n) space)

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        # dp[i] = True if index i is reachable from index 0
        dp = [False] * n
        dp[0] = True  # start position is always reachable

        for i in range(1, n):
            # Check if any earlier reachable position can jump to i
            for j in range(i):
                if dp[j] and j + nums[j] >= i:
                    dp[i] = True
                    break  # no need to check further

        return dp[n - 1]

JavaScript — DP Approach (O(n²) time, O(n) space)

function canJump(nums) {
    const n = nums.length;
    // dp[i] = true if index i is reachable from index 0
    const dp = new Array(n).fill(false);
    dp[0] = true;  // start position is always reachable

    for (let i = 1; i < n; i++) {
        // Check if any earlier reachable position can jump to i
        for (let j = 0; j < i; j++) {
            if (dp[j] && j + nums[j] >= i) {
                dp[i] = true;
                break;  // no need to check further
            }
        }
    }

    return dp[n - 1];
}

Python — Greedy Approach (O(n) time, O(1) space)

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # max_reach: farthest index reachable from any position visited so far
        max_reach = 0

        for i, jump in enumerate(nums):
            # If current index is beyond our frontier, we are stuck
            if i > max_reach:
                return False
            # Expand the frontier as far as this position can push it
            max_reach = max(max_reach, i + jump)

        # Completed the loop without getting stuck — last index is reachable
        return True

JavaScript — Greedy Approach (O(n) time, O(1) space)

function canJump(nums) {
    // maxReach: farthest index reachable from any position visited so far
    let maxReach = 0;

    for (let i = 0; i < nums.length; i++) {
        // If current index is beyond our frontier, we are stuck
        if (i > maxReach) return false;

        // Expand the frontier as far as this position can push it
        maxReach = Math.max(maxReach, i + nums[i]);
    }

    // Completed the loop without getting stuck — last index is reachable
    return true;
}

Complexity Analysis

For n = 10,000 (the constraint ceiling), O(n²) is 100 million operations — borderline in C++, frequently TLE in Python. The greedy solution is always safe.

Follow-up Questions

Jump Game II — LeetCode 45 (Minimum Jumps)

"What is the minimum number of jumps to reach the last index?"

The greedy solution extends naturally. Think of it as BFS level-by-level, where each "level" is one jump:

• Maintain jumps, current_end (the farthest index reachable with the current number of jumps), and farthest (the farthest index reachable if we take one more jump from anywhere in the current level).
• When i reaches current_end, increment jumps and set current_end = farthest.

Time: O(n), Space: O(1). The key insight is that you greedily take the jump that extends the frontier the most — always.

def jump(nums):
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):  # no need to jump from last index
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

Jump Game III — LeetCode 1306 (Reach Zero)

"From index start, you can jump left or right by nums[i] steps (not at most — exactly). Can you reach any index with value 0?"

Key differences:

• Jumps are bidirectional and exact (not maximum).
• Goal is reaching a zero, not a fixed endpoint.

Approach: BFS or DFS from start, tracking visited indices to avoid cycles. Each index i has neighbors i + nums[i] and i - nums[i]. Time: O(n), Space: O(n) for the visited set.

from collections import deque

def canReach(arr, start):
    n = len(arr)
    visited = set()
    queue = deque([start])

    while queue:
        i = queue.popleft()
        if arr[i] == 0:
            return True
        if i in visited:
            continue
        visited.add(i)
        for next_i in [i + arr[i], i - arr[i]]:
            if 0 <= next_i < n and next_i not in visited:
                queue.append(next_i)

    return False

Jump Game VI — LeetCode 1696 (Maximum Score)

"You can jump at most k steps at a time. Each landing adds nums[i] to your score. Maximize your score from index 0 to n-1."

This is a DP problem, not greedy:

dp[i] = max score to reach index i
dp[i] = nums[i] + max(dp[i-k], dp[i-k+1], ..., dp[i-1])

The inner max over a sliding window of size k is the bottleneck. Naive: O(nk). Optimal: use a monotonic deque (sliding window maximum) to reduce to O(n).

This is a great example of how the Jump Game family spans the full greedy/DP/deque spectrum.

This Pattern Solves

The "track a reachable frontier" pattern from Jump Game reappears in many other problems:

The unifying theme: reachable positions form a contiguous interval, so tracking the right endpoint of that interval is always sufficient.

Key Takeaway

Jump Game is the canonical example of recognizing when DP's O(n²) precision is unnecessary and a single greedy invariant — the max_reach frontier — captures everything. The algorithm is six lines, but the reasoning behind it (reachable positions always form a contiguous prefix) is the real answer interviewers are looking for. Master this one, and you will immediately see the same compression opportunity in a dozen harder problems: video stitching, minimum taps, interval covering, and all of Jump Game II through VI.

Next: Jump Game II — Minimum Jumps (LeetCode 45)