4.23.3 — House Robber

LeetCode 198 · Medium · ★ Blind 75

The problem

Each house holds some money. You cannot rob two adjacent houses. Return the most you can take.

[1,2,3,1]      →  4     (houses 0 and 2)
[2,7,9,3,1]    →  12    (houses 0, 2 and 4)

Restating the Problem: Imagine you are walking down a street with a bag, and you want to stuff as much cash in it as possible. The only rule is that the local neighborhood watch is set up so that if two neighboring houses are robbed on the same night, the alarm triggers. Thus, you must never pick two adjacent houses in the array. Your goal is to maximize your total loot without setting off the alarm.

Constraints to Note:

• The array can have up to 100 houses, which means anything slower than O(N^2) (like an exponential O(2^N) brute force) is going to fail on larger test cases.
• A house can have 0 money.
• The array can be empty or have just 1 house (we must handle these edge cases gracefully).

The Brute Force Approach

The most naive way to solve this is to just try every valid combination of houses. For every house, we branch into two universes: one where we rob it (and skip the next), and one where we skip it (and move to the next).

Since every house presents up to two choices, the recursion tree grows exponentially, giving a time complexity of O(2^N). With N = 100 houses, 2^{100} operations would take longer than the age of the universe to compute. The massive waste here is that we end up solving the exact same subproblems (e.g., "what's the max profit from house 5 onwards?") repeatedly. We need to eliminate this overlapping work.

Why greedy fails

The obvious greedy rule is "always take the biggest remaining house you are allowed to take". Break it in one line:

[2, 7, 9, 3, 1]

Greedy takes 9 first, which blocks 7 and 3, then takes 2 and 1 for a total of 12. That happens to be right here — so try:

[2, 1, 1, 2]

Greedy takes a 2, blocks its neighbour, takes the other 2 → 4. Correct again. Now:

[8, 10, 9]

Greedy takes 10, blocking both neighbours, total 10. The right answer is 8 + 9 = 17.

That is the structural tell from 4.22: taking a house removes an option later. A choice that constrains future choices is exactly what greedy cannot see, and it means DP.

The pattern

At each house you have exactly two options, and they cover everything:

• Rob it — then you must have skipped house i − 1, so you add nums[i] to the best total up to i − 2.
• Skip it — then your total is whatever the best was up to i − 1.

dp[i] = \max\big(nums[i] + dp[i-2],\ \ dp[i-1]\big)

Read aloud: the best up to house i is the better of robbing it — which forces you back two — or skipping it and keeping what you had.

"Take it or leave it, and taking it constrains what came before" is the single most common 1-D DP shape. Once you can write that line, most of this chapter is variations on it.

Think of it like being a picky eater at a buffet where eating one dish means you are too full to eat the dish right next to it. For every dish, you look at it and ask yourself: "Is the joy of eating this dish plus the joy from everything I ate before the previous dish greater than if I just skip this one and keep my total joy from the previous dish?" This is the core "aha moment". The choice at step i only depends on the optimal choices made at i-1 and i-2.

The solution

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob_prev, skip_prev = 0, 0           # dp[i-2], dp[i-1]

        for n in nums:
            rob_prev, skip_prev = skip_prev, max(n + rob_prev, skip_prev)

        return skip_prev

TypeScript

function rob(nums: number[]): number {
  let two = 0, one = 0;                      // dp[i-2], dp[i-1]

  for (const n of nums) {
    [two, one] = [one, Math.max(n + two, one)];
  }

  return one;
}

Two variables and one line. It is worth being able to read that line without hesitation:

• n + rob_prev — rob this house, adding to the best from two back.
• skip_prev — do not rob it, so keep the best from one back.
• The pair assignment shifts the window forward: what was "one back" becomes "two back", and the new answer becomes "one back".

Both variables start at 0, which handles the empty array and the first house with no special case. For nums = [5], one iteration gives max(5 + 0, 0) = 5. ✓

If the two-variable version is hard to trust, write the array first:

dp = [0] * (len(nums) + 1)
dp[1] = nums[0]
for i in range(2, len(nums) + 1):
    dp[i] = max(nums[i-1] + dp[i-2], dp[i-1])
return dp[-1]

Then collapse it. That is the honest order to work in, and showing the collapse is worth more than producing the tight version immediately.

Trace

[2, 7, 9, 3, 1]

house	value	rob it (n + two)	skip it (one)	new one
0	2	2 + 0 = 2	0	2
1	7	7 + 0 = 7	2	7
2	9	9 + 2 = 11	7	11
3	3	3 + 7 = 10	11	11
4	1	1 + 11 = 12	11	12

Answer 12. Notice house 3 is skipped because keeping the 11 beats taking 3.

Complexity

O(n) time, O(1) space.

Time Complexity Derivation: We loop through the array of n houses exactly once. Inside the loop, we are just doing constant-time operations (addition, max(), and simple variable reassignment). So, we do O(1) work N times, giving a total time complexity of O(N).

Space Complexity Derivation: Even though the theoretical DP table would be of size N (giving O(N) space), we noticed that we only ever look back exactly two steps (dp[i-1] and dp[i-2]). By just keeping track of those two previous values using rob_prev and skip_prev, we avoid allocating an array. Storing two integer variables takes O(1) extra memory.

Where this goes next

This recurrence appears everywhere once you know it:

• House Robber II — the houses form a circle, so the first and last are adjacent. Run this twice on two ranges. 4.23.4.
• House Robber III — a tree instead of a line. Each node returns two values: the best if it is robbed, and the best if it is not. Same idea, tree shape.
• Delete and Earn — deleting value v removes all v−1 and v+1. Bucket the values by number, and it becomes House Robber on the value axis. This reduction is the reason to learn this problem properly — the connection is not visible until you know what to look for.
• Maximum Sum of Non-Adjacent Elements, Best Sightseeing Pair — same skeleton.

What the interviewer will push on

"Why not greedy?" Give the [8, 10, 9] counterexample. Doing this before they ask is the strongest opening.

"What does dp[i] mean?" The best total considering the first i houses — not "the best if you rob house i". Being precise here prevents the usual confusion.

"Why do both variables start at 0?" It makes the empty and single-house cases fall out with no branch.

"O(1) space?" Two variables, and show the collapse from the array.

"What if the houses were in a circle?" House Robber II — two runs, excluding the first house in one and the last in the other.

"What if you also had to say which houses?" Keep the table and walk it backwards, checking at each step whether dp[i] came from robbing or skipping. Reconstructing the choice always needs the full table, which is the one real cost of the space optimisation.

One thing to volunteer: name the shape. "This is take-it-or-leave-it where taking constrains the previous choice — the standard 1-D DP." Then say which other problems reduce to it.

Next: 4.23.4 House Robber II — the same recurrence run twice, and the trick of removing a constraint by splitting the problem.