House Robber
Asked at Google, Microsoft, Apple, Databricks, Walmart
Problem
You are a robber planning to rob houses along a street. Each house has a certain amount of money, but adjacent houses have connected security systems. Find the maximum amount you can rob without triggering the alarm. This is a classic dynamic programming problem.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Databricks | Medium | View all Databricks questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
At each house, you have two choices: rob this house (add its value to the best result from 2 houses back) or skip it (carry forward the best result from the previous house).
The recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). dp[i] is the max money you can rob from houses 0 to i.
Why dp[i-2] + nums[i]? If you rob house i, you can't rob house i-1. So you add nums[i] to the best you could do ending at i-2.
Space optimization: you only need the last two dp values. Use two variables instead of an array. This brings space from O(n) to O(1).
Visual walkthrough for [2,7,9,3,1]:
dp[0] = 2 (only one house)
dp[1] = max(2, 7) = 7 (rob house 1 or house 0)
dp[2] = max(7, 2+9) = 11 (skip house 2 or rob houses 0,2)
dp[3] = max(11, 7+3) = 11 (skip house 3 or rob houses 1,3)
dp[4] = max(11, 11+1) = 12 (skip house 4 or rob houses 0,2,4)
Result: 12 (rob houses 0, 2, 4: 2+9+1=12)
Edge cases: single house (return its value), two houses (return the larger), empty array (return 0).
Optimal Approach
Step 1: Define dp[i] = max money robbed from houses 0 to i.
Step 2: Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
Step 3: For i from 2 to n-1:
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Either skip house i (keep dp[i-1]) or rob it (add nums[i] to dp[i-2]).
Step 4: Return dp[n-1].
Space optimization: use two variables prev1 (dp[i-1]) and prev2 (dp[i-2]).
For each num: new_prev1 = max(prev1, prev2 + num), prev2 = prev1.
Time: O(n). Space: O(1) optimized.
What Trips People Up in Real Interviews
Confusing this with "pick every other house." The constraint is no two adjacent houses, not every other house. You might skip houses non-uniformly.
Using recursion without memoization. That's O(2^n) and will time out. Use bottom-up DP or memoization to get O(n).
Forgetting that you can skip houses. At each house, you can either rob it (add to previous skip) or skip it (carry forward previous max).
Not handling edge cases: single house (rob it), two houses (rob the larger one).
Using a full dp array when only two variables are needed. Each position depends on the previous two values — use two variables for O(1) space instead of an O(n) array.
Solution Code
def rob(nums):
if not nums:
return 0
prev1, prev2 = 0, 0
for num in nums:
prev1, prev2 = max(prev1, prev2 + num), prev1
return prev1Frequently Asked Questions
What is the House Robber problem?
You are a robber planning to rob houses along a street. Each house has a certain amount of money, but adjacent houses have connected security systems. Find the maximum amount you can rob without triggering the alarm. This is a classic dynamic programming problem.
How do you solve House Robber?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask House Robber?
House Robber is asked at Google, Microsoft, Apple, Databricks, Walmart. It is a medium difficulty problem.
What are common mistakes on House Robber?
- Confusing this with "pick every other house." The constraint is no two adjacent houses, not every other house. You might skip houses non-uniformly.
- Using recursion without memoization. That's `O(2^n)` and will time out. Use bottom-up DP or memoization to get `O(n)`.
- Forgetting that you can skip houses. At each house, you can either rob it (add to previous skip) or skip it (carry forward previous max).
- Not handling edge cases: single house (rob it), two houses (rob the larger one).
- Using a full dp array when only two variables are needed. Each position depends on the previous two values — use two variables for `O(1)` space instead of an `O(n)` array.