How do you solve the house robber problem?

Q: How do you solve the house robber problem?

**Target Audience:** Beginners who have seen climbing stairs and want the next dynamic programming step. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A cat burglar in a cartoon walks down a street of houses at night. Each house has some cash inside. There is one rule: the houses on this street have connected alarms, so if she breaks into **two houses next to each other**, the alarm goes off. She wants the most money possible. Her first idea is "rob every other house": houses 1, 3, 5, … or houses 2, 4, 6, …, whichever totals more. On the street `[2, 1, 1,

The problem

Question presented to candidate: "You are a robber on a street of houses, each with some amount of money. Robbing two adjacent houses triggers the alarm. Given the amounts, return the most money you can rob tonight. Please write it in Python. If you finish early: what if the street is a circle?"

What a strong answer should cover:

The take-or-skip recurrence best[i] = max(best[i - 1], best[i - 2] + nums[i]), with base cases for zero and one house.
Why "every other house" and other greedy rules fail ([2, 1, 1, 2] → 4, not 3).
O(n) time with O(1) space via two rolling variables; the full table only when the chosen houses must be returned.
The circular variant: max of two line problems, excluding the first or the last house.
Python specifics: the one-line tuple shift prev, cur = cur, max(cur, prev + x), and that dp[-1] silently reads the last element instead of failing.

Clarifying questions expected:

"Is the street a line or a circle?"
"Do you want the maximum amount only, or also which houses?"
"Can amounts be zero or negative, and how large can the total get?"

Code / implementation expected: Yes — an O(n), O(1)-space Python function; reconstruction or the circular version as follow-ups.

dp

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners who have seen climbing stairs and want the next dynamic programming step. Difficulty: Medium Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A cat burglar in a cartoon walks down a street of houses at night. Each house has some cash inside. There is one rule: the houses on this street have connected alarms, so if she breaks into two houses next to each other, the alarm goes off. She wants the most money possible.

Her first idea is "rob every o

The solution is hidden so you can try first

13 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonHouse robber with the robbed houses recovered, against the every-other-house guess

Practice

PythonThe circular street (House Robber II) and a brute-force check on 300 random streets