LeetCode 198 – House Robber | Love Me Some Coding

House Robber is the dynamic programming problem that introduces a choice. Climbing Stairs counted ways and summed them; this one picks the better of two options at every step, which is the shape almost every optimisation DP takes. It is also the smallest problem where the greedy answer is obviously tempting and obviously wrong.

The problem

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

[1,2,3,1]     -> 4      houses 0 and 2
[2,7,9,3,1]   -> 12     houses 0, 2 and 4
[2,1,1,2]     -> 4      houses 0 and 3 -- NOT adjacent, and skipping two is allowed
[5]           -> 5
[2,1]         -> 2

[2,1,1,2] is the one to check. The answer skips two houses in a row, which several plausible-looking rules forbid — the constraint says you may not take adjacent houses, not that you must take every other one.

Why greedy fails

The greedy almost everyone proposes is "take every other house, starting from whichever end gives more" — the best of the even indices against the best of the odd ones. It sounds airtight, because the constraint is about adjacency and alternating never violates it.

[2, 1, 1, 2]

even indices (0, 2):  2 + 1 = 3
odd  indices (1, 3):  1 + 2 = 3
greedy answer: 3

optimum: houses 0 and 3  ->  2 + 2 = 4

The best solution skips two houses in a row, which no alternating rule can produce. That is the crux: the constraint forbids adjacency, it does not require you to take every other house, and any rule fixed in advance gives up the freedom to skip.

The general reason is the usual one — a local choice constrains what remains. Taking house i forfeits both neighbours, whose combined value may exceed it, and no greedy has a way to weigh that. So the decision has to be made with knowledge of the best outcome from each branch, which is dynamic programming.

The recurrence

Same reframing as every linear DP: not "which houses do I rob?" but

What is the most I can take from the first i houses?

At house i there are exactly two options, and no third:

skip it   -> best(i-1)                  whatever the previous houses gave
rob it    -> best(i-2) + nums[i]        i-1 is forfeited

best(i) = max( best(i-1), best(i-2) + nums[i] )

Compare that with Climbing Stairs' f(n-1) + f(n-2). Identical dependencies, different combiner: counting adds the branches, optimising takes the best of them. Recognising that one substitution is most of what makes the linear DP family feel small.

best(-1) = 0     nothing before the array
best(0)  = nums[0]

Java

class Solution {
    public int rob(int[] nums) {
        int twoBack = 0;    // best from houses up to i-2
        int oneBack = 0;    // best from houses up to i-1

        for (int money : nums) {
            // Either skip this house, or take it and add the best from two back.
            int current = Math.max(oneBack, twoBack + money);

            twoBack = oneBack;
            oneBack = current;
        }

        return oneBack;
    }
}

Both accumulators start at 0, which is correct here because the values are non-negative and robbing nothing is always an option. That also makes the empty array return 0 with no guard, and a single house return its own value on the first iteration.

The rotation order matters, as in Climbing Stairs: current must be computed from both old values before either is overwritten. Naming the variables for what they hold — rather than a and b — is how you catch getting it backwards.

Python

class Solution:
    def rob(self, nums: list[int]) -> int:
        two_back = one_back = 0

        for money in nums:
            two_back, one_back = one_back, max(one_back, two_back + money)

        return one_back

Tuple assignment evaluates the whole right-hand side first, so the ordering bug cannot be written. It is the same reason it was preferable in Climbing Stairs and Maximum Product Subarray.

Complexity

Approach	Time	Space
Try every subset	`O(2ⁿ)`	`O(n)`
DP array	`O(n)`	`O(n)`
Two variables	`O(n)`	`O(1)`

One pass, two integers. Every house must be examined, so linear is optimal.

The sequels, which are the point

House Robber II (213) arranges the houses in a circle, so the first and last are now adjacent. The trick is not a new recurrence — run this algorithm twice, once on nums[0..n-2] and once on nums[1..n-1], and take the better. Excluding one end each time makes the wrap-around constraint impossible to violate. Watch the single-house case, where both slices are empty.

House Robber III (337) puts the houses in a binary tree, and the same choice becomes "rob this node and skip its children, or skip it and take the best of each child". That is the return-two-values pattern from Balanced Binary Tree and Maximum Path Sum — each call returns a pair, robbed and not-robbed.

Delete and Earn (740) is this problem in disguise: bucket the values by number, and taking x forbids x−1 and x+1, which is adjacency on the value axis rather than the index axis. Spotting that reduction is more impressive than solving it directly.

What the interviewer is checking

That you state the two options at each house and note there is no third.
That you can explain why greedy has no way to weigh what a choice forfeits.
The base cases, and that both accumulators start at 0.
[2,1,1,2], where the answer skips two houses in a row.
Empty array and single house.
The two-variable compression, written in the right order.
That you can adapt it to the circular version without a new recurrence.