Jump Game Greedy Algorithm: Reach the Last Index in O(n)

You're given an array where nums[i] tells you how far you can jump forward from index i, and you're asked one question: can you reach the last index? It looks like a path-finding problem. You'll want BFS. You'll want DP tables. Don't. There's a single-pass greedy scan that answers it in O(n) with O(1) memory, and it's the whole point of LeetCode 55.

The trap that eats 20 minutes of interview time is simulating jumps. Candidates DFS through every landing spot, memoize GOOD/BAD states, and end up with O(n^2) code that times out on 10^4 elements. The greedy insight kills all of that: you don't care HOW you reached index i, only the farthest index reachable from everything up to i.

This walkthrough builds the brute force so you can explain it, then replaces it with the max-reach greedy. You'll get runnable Python, edge cases that break 80% of first attempts, and the follow-ups interviewers use to separate memorized code from real understanding.

Problem Walkthrough — What Jump Game Really Asks

LeetCode 55 gives you a 0-indexed array nums of length n. From index i you may jump to any index in [i+1, i+nums[i]]. Return True if any sequence of jumps lands on n - 1. Constraints: 1 <= n <= 10^4, 0 <= nums[i] <= 10^5.

Two observations shape everything. First, movement is forward-only, so the reachable set is always a prefix [0..R]. Second, you never need to know which path reached i — if i <= R, i is reachable, period. That collapses the entire problem into maintaining R, the max reach.

Walk through [2,3,1,1,4]: i=0 extends R to 2; i=1 extends R to 4, which covers the goal — done in 2 steps of the loop. Walk [3,2,1,0,4]: R climbs 3,3,3, then i=4 > R=3 — stuck at the zero wall. Return False.

Brute Force and DP — Why O(n²) Times Out

The honest brute force tries every jump from every index: DFS(i) returns True if any j in [i+1, i+nums[i]] reaches the end. That is O(2^n) paths — dead past n = 25.

Memoization helps: cache GOOD/BAD per index so each index is evaluated once, each evaluation scanning up to n successors. Complexity drops to O(n^2) time and O(n) space. For n = 10^4 that is ~10^8 operations — TLE in Python, borderline in C++.

Bottom-up DP (mark the last index GOOD, sweep right to left) has the same O(n^2) bound. All three versions share a flaw: they track per-index state when a single running maximum suffices.

Optimal Approach — The Max-Reach Greedy

Maintain max_reach, the farthest index reachable from everything scanned so far. At each i: if i > max_reach, i itself is unreachable — return False. Otherwise extend max_reach = max(max_reach, i + nums[i]). If max_reach >= n - 1, the goal is covered — return True.

Why is this safe? Because every index up to max_reach is reachable by definition, reaching i lets you reach everything up to i + nums[i], and no future index can unlock anything beyond repeated application of this rule. The greedy choice (always extend as far as possible) never harms future options — reach only grows.

Trace [2,3,1,1,4]: max_reach goes 0 → 2 → 4 → early exit True. Trace [3,2,1,0,4]: 0 → 3 → 3 → 3, then i=4 > 3 → False. One pass, one integer.

The Max-Reach Greedy Solution in Full Python

The implementation is six lines of logic. enumerate gives index and jump together; the guard rejects unreachable indices before their jump is ever read; the running max extends monotonically; the early exit fires the moment the goal is covered. Falling off the loop means every index was reachable, so return True.

The __main__ block encodes the five cases interviewers actually test: the two samples, the singleton, the zero-stepping-stone ([2,0,0] is True — you leap over zeros), and the late-zero trap ([1,1,0,1] is False). Run it locally before pasting into LeetCode.

from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """Greedy max-reach scan: O(n) time, O(1) space."""
        max_reach = 0
        last = len(nums) - 1
        for i, jump in enumerate(nums):
            if i > max_reach:
                return False
            if i + jump > max_reach:
                max_reach = i + jump
            if max_reach >= last:
                return True
        return True


if __name__ == "__main__":
    s = Solution()
    assert s.canJump([2, 3, 1, 1, 4]) is True
    assert s.canJump([3, 2, 1, 0, 4]) is False
    assert s.canJump([0]) is True
    assert s.canJump([2, 0, 0]) is True
    assert s.canJump([1, 1, 0, 1]) is False
    print("all checks passed")

Single-Element Arrays, Leading Zeros and Unreachable Tails

Edge cases cluster around zeros and boundaries. [0] → True (already there). [1,0] → True. [0,1] → False (stuck at start). [2,0,0] → True (jump clears both zeros). [1,1,0,1] → False (zero wall at index 2 with no jumper to clear it). [3,2,1,0,4] → False (the canonical trap).

Large values need no special handling: i + nums[i] up to ~2×10^5 fits any int type, and the algorithm never indexes at max_reach. Empty arrays violate the constraints (n >= 1), so don't branch for them — mention the assumption instead.

The nastiest case is a zero reachable only by exact landing versus cleared by a longer jump: [2,0,2,0,1] → True (index 0 jumps over index 1's zero to index 2). Code that simulates step-by-step lands on the zero and panics; max-reach sails over it.

Complexity — Why O(n) / O(1) Wins

Greedy max-reach: O(n) time — each index visited once, O(1) work each. O(1) extra space — one integer plus loop variables. This meets the n = 10^4 constraint with 1000x headroom.

Memoized DFS: O(n^2) time worst case (each index scans up to n successors), O(n) space for memo plus recursion stack — and Python's default recursion limit (1000) breaks before n = 10^4 anyway. Bottom-up DP: same O(n^2)/O(n). Backtracking without memo: O(2^n) — dead past n = 25.

Say this comparison out loud when you present the greedy. Interviewers score the complexity argument as highly as the code.