House Robber
Pick the most valuable set of houses on a street without ever choosing two neighbors. The standard first example of one-dimensional dynamic programming. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
Houses stand in a single row along a street, and nums[i] is the amount of cash in house i. A burglar wants to collect as much as possible, but neighboring houses share an alarm: taking from two adjacent houses on the same night sets it off.
Return the largest total the burglar can collect without ever taking from two houses next to each other.
Example 1
- Input
- nums = [4, 11, 3, 2, 9]
- Output
- 20
Take houses 1 and 4 (11 + 9). Taking every other house starting from 0 only gives 4 + 3 + 9 = 16.
Example 2
- Input
- nums = [6, 2, 4, 8, 3]
- Output
- 14
Take houses 0 and 3 (6 + 8). Skipping two houses in a row is allowed.
Example 3
- Input
- nums = [7]
- Output
- 7
Constraints
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 400
Practice
Runs 11 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked House Robber in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve House Robber
Pattern: 1D dynamic programming
Greedy rules like "take every other house" or "always grab the biggest" fail quickly; the first example beats both. What you can say for sure is something about the last house: either you take it, or you don't.
- If you skip house
i, the best total is whatever was best for houses0..i-1. - If you take house
i, you can't takei-1, so the best total isnums[i]plus the best for houses0..i-2.
So best(i) = max(best(i-1), best(i-2) + nums[i]). Each answer depends only on the two before it, which is the signal for a rolling pair of variables instead of a table.
Approach 1: Try every subset
Recursively decide take or skip for each house, skipping the next house after a take. It explores every valid combination, which grows exponentially (roughly Fibonacci in the length).
Time O(1.6ⁿ) · Space O(n)
Approach 2: Memoized recursion or a DP table
Store best(i) for every prefix so each is computed once, either top-down with a cache or bottom-up in an array of length n + 1.
Time O(n) · Space O(n)
Approach 3: Two rolling values
Keep prev (best up to two houses back) and curr (best up to the previous house), both starting at 0. For each amount x:
next = max(curr, prev + x).- Shift:
prev = curr,curr = next.
After the loop, curr is the answer. Starting both at 0 handles a single house without a special case.
Time O(n) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Try every subset | O(1.6ⁿ) | O(n) |
| Memoized recursion or a DP table | O(n) | O(n) |
| Two rolling values | O(n) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
House Robber solution in Python
def rob(nums: list[int]) -> int:
prev, curr = 0, 0 # best up to i-2, best up to i-1
for x in nums:
prev, curr = curr, max(curr, prev + x)
return currHouse Robber solution in JavaScript
function rob(nums) {
let prev = 0; // best up to i-2
let curr = 0; // best up to i-1
for (const x of nums) {
const next = Math.max(curr, prev + x);
prev = curr;
curr = next;
}
return curr;
}Common mistakes
- Assuming the answer is the larger of the even-index sum and the odd-index sum. [6, 2, 4, 8, 3] needs indices 0 and 3.
- Updating `prev` before computing the new value, which mixes up which house is "two back".
- Special-casing arrays of length 1 or 2 with index lookups that crash on the shorter input. Zero-initialized rolling variables avoid this.
- Returning `max(nums)` style answers for short arrays and forgetting that houses with 0 are valid inputs.
What interviewers look for
Start from the decision on the last house and say the recurrence out loud: "skip it and keep best(i-1), or take it and add it to best(i-2)." That sentence is what the interviewer is waiting for; the code follows from it.
Then show the progression: recursion, add memoization, notice each step reads only two previous values, and collapse to two variables. Naming that progression shows you can apply DP to problems you haven't seen.
Follow-up questions
What if the houses form a circle, so the first and last are neighbors?
You can't take both ends, so run the same linear solution twice: once on houses 0..n-2 and once on 1..n-1, and return the larger. Handle n = 1 separately.
How would you return which houses were chosen?
Keep the full DP array, then walk backwards: if best[i] equals best[i-1], house i was skipped; otherwise it was taken and you jump to i-2.
What if the houses are nodes in a binary tree and parent-child pairs are adjacent?
Do a post-order traversal returning two values per node: the best total if you take the node (its value plus both children's "skip" totals) and if you skip it (the sum of each child's best of take or skip).
Companies that ask House Robber
House Robber is tagged by 118 companies in our interview dataset. The score shows how often it comes up at each company.
- Cisco100%
- Ihs Markit100%
- Cars24100%
- Harman International98%
- Highradius96%
- Whoop95%
- Appier93%
- Amperity90%
- Freecharge89.2%
- Personio87%
- Exact Sciences86%
- Atos85%
- Databricks83.7%
- Dotdash Meredith82%
- Weedmaps80%
- Telus80%
- Xero77%
- Red Hat76%
- Derivco76%
- Grab75.7%
- Panasonic75%
- Sift75%
- Rocket Software74%
- ADP73%
and 94 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required