p56 — House Robber

Source: LeetCode 198 · Medium · Topics: 1D DP, Greedy-vs-DP discrimination Companies (2024–2025): Amazon (very high), Google (high), Meta (high), Microsoft (high), LinkedIn (medium) Loop position: The “first real DP” warm-up. Tests whether you can derive a recurrence cold, not whether you’ve memorized one.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/house-robber/

STOP. 15-min timer.

3. Prerequisite Concepts

1D DP recurrence: state, transition, base, evaluation order, answer location.
LC 70 Climbing Stairs (the trivial sibling).

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Pick a subset of indices with no two adjacent; maximize sum.

2. Clarify: All non-negative? (Yes.) Empty? (Return 0.) Single house? (Return nums[0].)

3. Constraints: n ≤ 100 on LC but the algorithm is O(n) regardless.

4. Examples: [1,2,3,1] → 4; [2,7,9,3,1] → 12; [2,1,1,2] → 4.

5. Brute force: Recursion with (i, can_take) state — exponential without memoization, O(n) with.

6. Target: O(n) time, O(1) space.

7. Pattern: 1D DP, “include vs skip.”

8. Develop: see solution.py.

9. Test: empty; single; two; alternating; all equal; strictly increasing.

6. Deeper Insight

6.1 The recurrence

Define dp[i] = max money robbing among houses 0..i inclusive. At house i:

Skip: carry dp[i-1].
Rob: add nums[i] to dp[i-2] (the most we could have robbed without using house i-1).

So dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Base: dp[0] = nums[0], dp[-1] = 0.

“Just rob every even-indexed house” — fails on [2,1,1,2] (greedy = 3, optimal = 4 by robbing 0 and 3). “Just rob the biggest, then the next biggest non-adjacent” — fails because adjacency forces a chain of corrections.

The exchange-argument intuition: a globally optimal choice at house i may require not robbing the locally biggest house. DP is the right hammer.

6.3 Space compression to O(1)

Since dp[i] depends only on dp[i-1] and dp[i-2], keep two rolling variables. This is the universal trick for 1D DP with constant recurrence depth.

6.4 Variants (Hint: they’re all the same DP)

LC 213 House Robber II (circular row): solve twice — once excluding house 0, once excluding house n-1; take max. Why: if you rob both ends, they’re adjacent in the circle.
LC 337 House Robber III (binary tree): DP on tree. Each node returns (rob, skip); parent picks max(child.rob, child.skip) + ....
LC 740 Delete and Earn: collapse to House Robber via “for each value v, total = v * count(v); rob the array indexed by v.”

6.5 Why this problem is the perfect DP onboarding

It has the simplest non-trivial recurrence (two prior states). No grid, no string, no graph. If you can’t derive it cold, you don’t know DP — go re-read the 1D DP chapter. If you can, every harder DP in this week is “same idea, more dimensions.”

7. Anti-Pattern Analysis

Greedy (rob every other) — wrong (counter-example above).
Sort and pick — destroys adjacency; doesn’t even make sense.
Memoized DFS without space compression — O(n) memory for no reason; interviewer notices.
Off-by-one with dp[i-2] when i = 1 — handle dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) explicitly OR use sentinel prev2 = 0.
dp[i] = dp[i-2] + nums[i] (forgot the max with dp[i-1]) — common bug; passes some tests by luck.

8. Skills & Takeaways

1D DP template: state → transition → base → order → answer.
“Include or skip” pattern: appears in subsequence problems, subset sums, knapsack.
Recognize when greedy ≠ optimal via tiny counter-example.

9. When to Move On

Solve cold in 7 minutes with O(1) space.
Derive the recurrence verbally in under 30 seconds.
Sketch LC 213 (circular) and LC 337 (tree DP) variants.
Explain why greedy fails with a 4-element counter-example.

10. Company Context

Amazon: L4/L5 phone screen. Common warm-up. Bar Raiser asks for O(1) space immediately.
Google: L4 phone screen; followed by LC 213 in onsite.
Meta: Phone screen; expect a follow-up of LC 337.
Microsoft: L62 phone screen; classic.
LinkedIn: Used as the first onsite problem to calibrate DP fluency.

Scorecard phrase for strong: “Derived recurrence cleanly, compressed to O(1) without prompt, sketched the tree-DP variant.”

11. Interviewer’s Lens

Signal	Junior	Mid	Senior	Staff+
Recurrence	Memorized	Derived but hesitant	Derived in <30s	+ space compression + variant generalization
Edge cases	Misses empty	Handles empty + single	Proactive	+ variant edge cases articulated
Variants	Doesn’t know	Knows LC 213	Solves LC 213	+ Tree DP version + reduction LC 740

12. Level Delta

Mid (L4): 2D dp[] array, O(n) space, correct.
Senior (L5): O(1) space; derives recurrence verbally; mentions LC 213 by name.
Staff (L6): All above + tree-DP variant LC 337 derived live + space compression on tree version.
Principal (L7+): All above + discusses adversarial input distributions; mentions reduction LC 740; connects “include or skip” to weighted independent set on path/tree graphs (which is what this problem literally is).

13. Follow-up Q&A

Q1: Circular row (LC 213). How? A1: If we rob house 0, we cannot rob house n-1, so the optimal on nums[0..n-2]. If we don’t rob house 0, the optimal is on nums[1..n-1]. Take max of the two House Robber subproblems. O(n) time.

Q2: Binary tree (LC 337). How? A2: Tree DP. For each node, return (rob, skip):

rob = node.val + left.skip + right.skip
skip = max(left.rob, left.skip) + max(right.rob, right.skip) Root answer = max(root.rob, root.skip). O(n) total.

Q3: What if nums[i] can be negative? A3: Then dp[i] = max(dp[i-1], dp[i-2] + nums[i], dp[i-2]) — skipping a negative is an option distinct from “can’t rob adjacent.” Or equivalently max(0, nums[i]) at every house since you’d never rob a negative-value house.

Q4: Streaming variant — houses arrive one at a time, what’s the max so far? A4: Just maintain rolling prev2, prev1; emit max(prev1, prev2 + nums[i]) after each new house. O(1) per update.

Q5: K-non-adjacent (no two robbed houses within distance K)? A5: dp[i] = max(dp[i-1], dp[i-K-1] + nums[i]). Same template, deeper history window.

14. Solution Walkthrough

See solution.py. Two functions:

rob_dp_array — O(n) time, O(n) space, full DP array (for the explanatory variant).
rob_o1_space — O(n) time, O(1) space, rolling two variables.
rob_brute — exponential, for stress test (n ≤ 18).

15. Beyond the Problem

Principal code review: “This problem is the smallest possible weighted-independent-set on a path graph. The fact that we solve it in O(n) one-pass is a foreshadowing of why DP on trees is also linear (you visit each node once, you compute (include, exclude) for each, you propagate). When you understand that House Robber, House Robber III, and Maximum Independent Set on a tree are the same algorithm with different graph topologies, you’ve crossed from ‘pattern matcher’ to ‘reasoner.’ That’s the hinge from L5 to L6.”

LeetCode Interview — Extreme Coding