Skip to content

154 — Jump Game II

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

154 — Jump Game II

LeetCode 45 · Medium. You are given an array of integers nums, where nums[i] represents your maximum jump length at index i. You are initially positioned at index 0. Return the minimum number of jumps required to reach the last index. You may assume you can always reach it.

🍽️ Intuition

Jump Game only asked "can you get there at all?" — this one asks "in how few jumps?" Picture the reachable indices as expanding in waves, like ripples from a stone dropped in water: everywhere reachable in one jump forms the first wave, everywhere reachable from any index in that wave (in one more jump) forms the second wave, and so on. That's exactly BFS "level by level" expansion, except there's no need to build an actual graph or queue — the boundary of each wave is just a range of indices, and the next wave's boundary is the farthest any index in the current wave can reach. Counting waves until the last index falls inside one gives the minimum number of jumps.

🚩 Pattern-Recognition Cue

"Minimum number of jumps to reach the end" (as opposed to Jump Game's yes/no reachability) is the level-by-level greedy tell: track the current jump's reachable boundary and the farthest the next jump could reach, incrementing a jump counter each time the scan crosses the current boundary — the same shape as counting BFS levels outward from the start index, but computed with two running boundary values instead of an explicit queue.

🐢 Brute Force

Recurse from the current index, trying every possible jump length and taking the minimum over all of them, with no memoization.

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

    func minJumps(from index: Int) -> Int {
        if index >= n - 1 { return 0 }

        let maxJump = min(nums[index], n - 1 - index)
        guard maxJump > 0 else { return Int.max }

        var best = Int.max
        for step in 1...maxJump {
            let sub = minJumps(from: index + step)
            if sub != Int.max {
                best = min(best, sub + 1)
            }
        }
        return best
    }

    return minJumps(from: 0)
}

// smoke test
print(jumpBruteForce([2, 3, 1, 1, 4]))   // 2
print(jumpBruteForce([2, 3, 0, 1, 4]))   // 2
print(jumpBruteForce([1]))               // 0

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 current jump's reachable boundary (currentEnd) and the farthest any index up to that boundary could reach (farthest). Every time the scan reaches currentEnd, one more jump is spent and the boundary advances to farthest.

func jump(_ nums: [Int]) -> Int {
    let n = nums.count
    guard n > 1 else { return 0 }

    var jumps = 0
    var currentEnd = 0
    var farthest = 0

    for i in 0..<(n - 1) {
        farthest = max(farthest, i + nums[i])

        if i == currentEnd {
            jumps += 1
            currentEnd = farthest
            if currentEnd >= n - 1 { break }
        }
    }

    return jumps
}

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

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

🔑 The Key Insight

The brute force treats "which exact jump length to take" as a decision worth branching over at every index, so the same later indices get re-solved independently through every different combination of jump lengths that reaches them. The optimal version notices that within a single jump's reach, it never matters which specific index the next jump launches from — only the farthest any of them can collectively reach matters, because that farthest reach dominates every other option for continuing further. That's precisely the BFS-frontier idea: process all indices reachable within the current jump count as one "level," compute the single farthest boundary the next jump could achieve from anywhere in that level, and only then advance — collapsing what would be an exponential branching search into one linear scan with two tracked boundaries.

🔗 Related Chapters

  • Greedy — currentEnd and farthest are running state updated once per index and never revisited, the same irrevocable-local-choice shape as Jump Game's single farthest tracker.
  • BFS — the current-jump boundary and next-jump boundary mirror BFS's "current level" and "next level" frontiers expanding outward from the start index, just computed via index arithmetic instead of an explicit queue.
  • Arrays and Strings — both versions scan nums as a plain backing array from left to right.

🧸 Memory Sentence

Jump Game II is BFS without the queue — track the current jump's reach boundary and the farthest the next jump could push it, and spend a jump every time the scan crosses that boundary.

✅ Check Your Understanding

  1. Why does incrementing jumps happen exactly when i == currentEnd, rather than as soon as farthest changes?
  2. Trace jump([2, 3, 1, 1, 4]) step by step. What are the values of currentEnd and farthest right before each jump increment?
  3. The loop runs for i in 0..<(n - 1) rather than 0..<n. Why is it correct — and important — to stop one index short of the end?

⬅️ Previous: Jump Game · Next: Gas Station ➡️

Clone this wiki locally