House Robber
On this page
Problem statement
A row of houses each holds some money (a non-negative integer). Choose houses to take money from so that no two chosen houses are next to each other, and return the largest total you can collect.
The textbook first problem for one-dimensional dynamic programming: each house is a yes/no choice whose effect reaches exactly one step ahead. Interviewers like it because the greedy guesses look right and are wrong. Original problem: LeetCode 198.
Example

Input: [5, 1, 2, 10, 6, 2]
Output: 17 # houses 0, 3, 5: 5 + 10 + 2
Input: [2, 9]
Output: 9
Constraints (assumed)
- 1 ≤ n ≤ 100,000 houses; 0 ≤ value ≤ 10,000.
What this question tests
- Defining a state ("best total using the first i houses") and a recurrence from a take/skip choice.
- Seeing why greedy picks (largest first, every other house) fail.
- Shrinking the table to O(1) space.
Questions to ask first
- Can values be zero or negative? (Here: non-negative; with negatives you'd simply never take those houses.)
- Is the row a line or a circle? (Here: a line. The circle is a classic follow-up.)
- Do you want the total or the chosen houses? (Here: the total.)
- Can the list be empty? Return 0.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.