Skip to content

131 — House Robber

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

131 — House Robber

LeetCode 198 · Medium. You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, and the only constraint stopping you from robbing each of them is that adjacent houses have connected security systems, and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money at each house, return the maximum amount of money you can rob tonight without alerting the police.

🍽️ Intuition

Stand at house i and ask: what's the best I can do considering only houses 0 through i? There are exactly two options — skip house i entirely and keep whatever was best through house i-1, or rob house i and add its money to the best total through house i-2 (since robbing i forbids i-1). Whichever of those two options is bigger is the best answer through house i. Notice that this decision never needs to know anything about houses further back than i-2 — the whole history of choices collapses into just two running numbers.

🚩 Pattern-Recognition Cue

"Maximize the total, but you can't pick two adjacent items" is the House Robber tell: a binary take-or-skip decision at every position, where taking an item locks out only its immediate neighbor. Whenever the constraint is "no two adjacent," the recurrence needs to look back exactly two positions — dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

🐢 Brute Force

Recurse from every house, trying both "skip this house" and "rob this house" at each step, with no memoization — the same suffix gets fully re-solved from multiple different starting points.

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

    func bestFrom(_ i: Int) -> Int {
        if i >= n { return 0 }
        let skip = bestFrom(i + 1)
        let take = nums[i] + bestFrom(i + 2)
        return max(skip, take)
    }

    return bestFrom(0)
}

// smoke test
print(robBruteForce([1, 2, 3, 1]))       // 4
print(robBruteForce([2, 7, 9, 3, 1]))    // 12
print(robBruteForce([2, 1, 1, 2]))       // 4

Big-O: O(2^n) time — every house branches into "skip" and "take," and the same later houses get re-explored from both branches. O(n) space for the recursion stack.

🚀 Optimal

Walk forward through the houses, keeping only the best total through the previous house and the one before that — the classic two-state rolling tabulation.

func rob(_ nums: [Int]) -> Int {
    guard !nums.isEmpty else { return 0 }
    guard nums.count > 1 else { return nums[0] }

    var prev2 = 0        // best total through house i-2 (0 houses back = 0)
    var prev1 = nums[0]  // best total through house i-1

    for i in 1..<nums.count {
        let current = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = current
    }

    return prev1
}

// smoke test — same cases as the brute force
print(rob([1, 2, 3, 1]))       // 4
print(rob([2, 7, 9, 3, 1]))    // 12
print(rob([2, 1, 1, 2]))       // 4

Big-O: O(n) time — one forward pass, O(1) work per house. O(1) extra space — two rolling variables, no recursion stack.

🔑 The Key Insight

The brute force and the optimal version consider the exact same two choices at every house — skip it, or rob it and skip the one before — but the brute force pays for that choice fresh every time a house is reached, and because "skip" and "take" both eventually funnel through the same later houses, those houses get re-solved an exponential number of times. The optimal version tabulates forward instead, so "best total through house i" is computed once and carried forward as prev1, ready to be reused the instant house i+1 needs it. Since the recurrence only ever reaches back two houses, that tabulation needs just two rolling variables — no array, no recomputation, and the exponential blowup disappears entirely.

🔗 Related Chapters

  • 1D Dynamic Programming — this is chapter 26's own worked example: the take-or-skip recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]) collapsed to two rolling variables.
  • Arrays and Strings — the optimal solution is a single left-to-right sweep over nums, the same array-traversal shape every rolling-DP problem in this batch shares.

🧸 Memory Sentence

House Robber is the take-or-skip walk down a street — at every house, either keep the best total from next door, or take this house's money plus the best total from two doors back.

✅ Check Your Understanding

  1. Why does prev2 start at 0 rather than at nums[0], and what would break if it started at nums[0] instead?
  2. Trace rob([2, 7, 9, 3, 1]) by hand: what are prev1 and prev2 after each loop iteration, and which houses does the optimal path actually rob?
  3. The brute force computes bestFrom(i + 2) from within the "take" branch at house i. Explain concretely why bestFrom(3), for instance, ends up being called from more than one earlier house, and why that repetition disappears in the rolling version.

⬅️ Previous: Min Cost Climbing Stairs · Next: House Robber II ➡️

Clone this wiki locally