153 — Jump Game

153 — Jump Game

LeetCode 55 · Medium. You are given an integer array nums. You are initially positioned at the array's first index, and each element represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.

---

🍽️ Intuition

Forget trying to plan out an exact sequence of jumps — that's a lot of bookkeeping for a question that only asks yes-or-no. Instead, scan left to right and track a single number: the farthest index reachable so far, using any combination of jumps made up to this point. At each index, if that farthest reach is still at least as far as the current index, this index is reachable, and its own jump length might push the frontier even further out. The moment the scan reaches an index beyond the farthest-so-far frontier, no sequence of earlier jumps — however cleverly chosen — could have gotten here, so the answer is false. Otherwise, if the frontier ever reaches or passes the last index, the answer is true.

---

🚩 Pattern-Recognition Cue

"Can you reach the last index?" with per-position maximum jump lengths is the reachability-frontier tell: track "the farthest index reachable so far" as a single running number, extend it greedily while scanning forward, and never need to remember which jump produced that maximum — only the maximum itself.

---

🐢 Brute Force

Recurse from the current index, trying every possible jump length (largest first) and recursing on each, with no memoization — the same indices get re-explored via many different jump sequences.

func canJumpBruteForce(_ nums: [Int]) -> Bool {
    let n = nums.count

    func canReachEnd(from index: Int) -> Bool {
        if index >= n - 1 { return true }

        let maxJump = nums[index]
        guard maxJump > 0 else { return false }

        for step in stride(from: maxJump, through: 1, by: -1) {
            if canReachEnd(from: index + step) {
                return true
            }
        }
        return false
    }

    return canReachEnd(from: 0)
}

// smoke test
print(canJumpBruteForce([2, 3, 1, 1, 4]))   // true
print(canJumpBruteForce([3, 2, 1, 0, 4]))   // false
print(canJumpBruteForce([0]))               // true

Big-O: O(2^n) time in the worst case — each index can branch into up to n further indices, and many different jump sequences re-explore the same later indices independently. O(n) space for the recursion stack.

---

🚀 Optimal

Track the farthest index reachable so far, extending it greedily at every step.

func canJump(_ nums: [Int]) -> Bool {
    var farthest = 0

    for i in 0..<nums.count {
        if i > farthest {
            return false
        }
        farthest = max(farthest, i + nums[i])
    }

    return true
}

// smoke test — same cases as the brute force
print(canJump([2, 3, 1, 1, 4]))   // true
print(canJump([3, 2, 1, 0, 4]))   // false
print(canJump([0]))               // true

Big-O: O(n) time — a single left-to-right pass over nums. O(1) extra space.

---

🔑 The Key Insight

The brute force asks "starting from here, does some sequence of jumps reach the end?" for every index reached along every possible path, re-deriving the same answer for the same index over and over via different routes. The optimal version notices that the only thing that ever matters about "everywhere reachable so far" is the single farthest point among them — an index reachable via a shorter jump can never let you go further than an index reachable via a longer one, so there's no benefit to tracking anything except the maximum. Collapsing "every index reachable so far" down to "the farthest index reachable so far" turns an exponential search over jump sequences into one linear scan.

---

🔗 Related Chapters

• Greedy — this is the canonical worked example in the Greedy pattern chapter: farthest = max(farthest, i + nums[i]) is a running local choice made once per index and never revisited.
• Arrays and Strings — the scan reads nums left to right as a plain backing array, the same traversal shape used across every greedy array problem in this batch.

---

🧸 Memory Sentence

Jump Game is a single farthest-reach tracker — scan left to right, extend the farthest reachable index at every step, and fail only the moment the scan itself outruns that frontier.

---

✅ Check Your Understanding

1. Why does if i > farthest { return false } correctly detect an unreachable index, rather than needing to check nums[i] itself?
2. Trace canJump([3, 2, 1, 0, 4]) step by step. At which index does farthest stop growing, and why does the scan fail before ever looking at the final 4?
3. Why is it safe for farthest to only ever grow (never shrink) as the scan proceeds?

---

⬅️ Previous: Maximum Subarray · Next: Jump Game II ➡️