House Robber Problem: How Do You Solve It?
Learn to solve the house robber problem with dynamic programming, the include/exclude recurrence, and the circular variant.
Expected Interview Answer
The house robber problem — maximizing loot from a row of houses without robbing two adjacent ones — is solved with dynamic programming where, at each house, you take the better of skipping it (carrying forward the best total so far) or robbing it (its value plus the best total from two houses back), computed in O(n) time and O(1) space.
Define dp(i) as the maximum loot achievable considering houses 0 through i; at house i you either skip it, keeping dp(i-1), or rob it, adding its value to dp(i-2) since the adjacent house i-1 is now off-limits. Taking the max of these two options at every house builds the optimal solution bottom-up without ever needing to backtrack or reconsider a decision. The base cases are dp(0) equal to the value of the first house and dp(1) equal to the max of the first two houses. A common variant — houses arranged in a circle — is solved by running the linear version twice, once excluding the first house and once excluding the last, then taking the max, since a circular arrangement makes house 0 and house n-1 adjacent.
- O(n) time with a single left-to-right pass
- O(1) space by tracking only two rolling maximums
- Extends cleanly to the circular-houses variant
- Demonstrates the "include vs exclude" DP decision pattern
AI Mentor Explanation
Choosing which balls in an over to attack for maximum runs, where you cannot attack two consecutive balls without the bowler adjusting and shutting down the next one, mirrors the house robber problem exactly. At each ball, the batter either lets it go, keeping the best score achieved so far, or attacks it, adding its potential runs to the best score from two balls earlier since the previous ball is now off-limits. A batter who tries to attack every single ball risks the bowler tightening the line after each aggressive shot, capping the actual total lower than a selective approach. Choosing the better of "skip" or "attack plus two-balls-back total" at each delivery is exactly the include-versus-exclude recurrence that maximizes the innings score.
Step-by-Step Explanation
Step 1
Define the state
dp(i) = maximum loot achievable using houses 0..i, respecting the no-adjacent-robbery constraint.
Step 2
Write the recurrence
dp(i) = max(dp(i-1), dp(i-2) + house[i]) — skip house i, or rob it and add to the total from two houses back.
Step 3
Set base cases
dp(0) = house[0]; dp(1) = max(house[0], house[1]).
Step 4
Handle the circular variant if asked
Run the linear solution twice — once excluding the last house, once excluding the first — and take the max, since house 0 and house n-1 are adjacent in a circle.
What Interviewer Expects
- Correctly derive dp(i) = max(dp(i-1), dp(i-2) + house[i])
- Identify and handle the base cases dp(0) and dp(1) correctly
- Optimize space from an O(n) array to O(1) rolling variables
- Discuss (or solve) the circular houses variant when prompted
Common Mistakes
- Trying a greedy approach (always rob the higher of two adjacent houses), which fails on counterexamples
- Forgetting the "skip" option and only considering robbing every other house in a fixed pattern
- Mishandling the base case for a single house or an empty house list
- Not recognizing the circular variant requires two separate linear passes
Best Answer (HR Friendly)
“The house robber problem is about maximizing the total money you can steal from a row of houses without robbing two houses next to each other, since that triggers an alarm. At each house I decide between skipping it, which keeps my current best total, or robbing it, which adds its value to my best total from two houses back — and I always take whichever choice gives more, moving left to right in linear time.”
Code Example
def rob(nums: list[int]) -> int:
prev2, prev1 = 0, 0
for value in nums:
prev2, prev1 = prev1, max(prev1, prev2 + value)
return prev1
# rob([2, 7, 9, 3, 1]) -> 12 (rob houses 0, 2, 4)Follow-up Questions
- How would you solve the circular version where the first and last houses are adjacent?
- How would you also return which specific houses were robbed, not just the max total?
- Why does a greedy "always pick the larger neighbor" strategy fail here?
- How would you adapt this if you could rob up to two houses in a row but not three?
MCQ Practice
1. What is the recurrence relation for the house robber problem?
At each house you either skip it (dp(i-1)) or rob it and add to the total two houses back (dp(i-2) + house[i]), taking the max.
2. How is the circular houses variant typically solved?
Since house 0 and house n-1 are adjacent in a circle, you solve two linear subproblems that each exclude one end, then take the better result.
3. Why does a greedy approach fail on the house robber problem?
A locally optimal choice can prevent access to a much larger value further down the row, so only full DP guarantees the global optimum.
Flash Cards
What is the house robber recurrence? — dp(i) = max(dp(i-1), dp(i-2) + house[i]).
What is the time complexity of the optimal house robber solution? — O(n) time, O(1) space with rolling variables.
How do you solve the circular house robber variant? — Run the linear algorithm twice (excluding first house, then excluding last house) and take the max.
Why does greedy fail on house robber? — A locally larger neighbor can block access to a much larger value further along the row.