# House Robber > Rob the most money from a row of houses without hitting two neighbours. Build the best total house by house, where each house either adds its loot to the best from two houses back, or is skipped. - Track: DSA (Dynamic Programming) - Level: Medium - Format: Step-through player - Author: Aayush Ostwal - Published: 24 October 2026 - Topics: Dynamic programming, 1D DP - LeetCode: https://leetcode.com/problems/house-robber/ - Canonical URL: https://compoundengineer.com/library/dsa/house-robber Dynamic programming · 1D Medium · O(n) time · O(1) space ## Problem You are a robber planning to rob houses along a street. Each house i holds nums[i] dollars. Adjacent houses have a connected security system: if you rob two houses that are next to each other, the alarm goes off. Return the maximum amount you can rob without robbing two adjacent houses. Example 1 Input: nums = [1, 2, 3, 1] Output: 4 (rob house 0 and house 2: 1 + 3) Example 2 Input: nums = [2, 7, 9, 3, 1] Output: 12 (rob houses 0, 2 and 4: 2 + 9 + 1) Constraints 1 ≤ nums.length ≤ 100 0 ≤ nums[i] ≤ 400 ## Brute force Picture a street of houses in a row. Each house has some money inside. You may rob any houses you like, but if you rob two houses that stand next to each other , the alarm goes off. How much can you take? - Each house holds a known amount of money. - You cannot rob two neighbouring houses. - Return the largest total you can take. The direct idea: stand at the first house and make a choice. Either rob it and jump two houses ahead (the next house is off limits), or skip it and move one house ahead. Try both, and keep the better total. ### The problem with it Every house splits the search in two, so n houses give about 2 n paths. It also repeats itself: "what is the best I can do from house 5 onwards?" is asked again from every path that reaches house 5, and the answer is always the same. ## How to think your way to the optimal solution The same small question keeps coming back: "what is the best total using only the first few houses?" So let us answer it once for each house, going from left to right, and write the answers down. If we know the best totals for the earlier houses, what is the best total up to this house? Let dp[i] be the best total using houses 0 to i . At house i there are only two choices: - Skip it. Then the best is whatever we had for the houses before it: dp[i − 1]. - Rob it. Then house i − 1 is off limits, so we add this house's money to the best total from two houses back: dp[i − 2] + nums[i]. We take the bigger of the two. That is the whole idea: dp[i] = max(dp[i − 1], dp[i − 2] + nums[i]) . The first two cells are special: dp[0] is the first house, and dp[1] is the larger of the first two houses, because we can only rob one of them. ## The optimal solution ### Approach 1: a table - If there is only one house, rob it. - Set dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]). - For each later house i: skip = dp[i − 1] and take = dp[i − 2] + nums[i]. - take is bigger⟶rob it: dp[i] = take otherwise⟶skip it: dp[i] = skip - The answer is the last cell. By hand , with houses [2, 7, 9, 3, 1] : - dp[0] = 2. One house: rob it. - dp[1] = 7. Two houses, pick the larger: 7. - House 2 (9). Skip gives 7. Rob gives 2 + 9 = 11. Take the 11. - House 3 (3). Skip gives 11. Rob gives 7 + 3 = 10. Skip is better, so it stays 11. - House 4 (1). Skip gives 11. Rob gives 11 + 1 = 12. Take the 12. The answer is 12 : houses 0, 2 and 4. Press Play to watch the table fill, with the two values it compares at each house. ### Approach 2: two numbers The idea. Look at what each cell reads: only the one before it and the one two before it. Older cells are never looked at again. So we do not need the whole table. Two variables are enough: prev1 (the best up to the previous house) and prev2 (the best up to the house before that). - Start both at 0, as if there were no houses. - For each house with money x: the new best is max(prev1, prev2 + x). Then shift: prev2 becomes the old prev1. - The answer is prev1. By hand , [2, 7, 9, 3, 1] , showing (prev2, prev1) after each house: house 2 gives (0, 2). House 7 gives (2, 7). House 9 gives (7, 11). House 3 gives (11, 11). House 1 gives (11, 12). The answer is the last prev1 , 12 . Cost. Same time, but only two numbers of memory. ## Complexity analysis | Approach | Time | Space | | --- | --- | --- | | Try every choice | 2n | O(n) | | --- | --- | --- | | A table | O(n) | O(n) | | --- | --- | --- | | Two numbers | O(n) | O(1) | | --- | --- | --- | O(n) Time. Here's why: we visit each house once, and at each house we do one comparison and one addition. That takes the same small time for every house. O(1) Space (two numbers). Two variables, no matter how many houses. The table version uses O(n) because it stores one number per house. ## Interviewer follow-ups These are the questions that usually come next. Open one to see an answer you could say out loud. "The street is a circle. The last house is next to the first." What they are checking Whether you can reuse your solution on a changed problem instead of starting again. This is the well-known "House Robber II". A strong answer Now the first and last house cannot both be robbed. So any good plan leaves out at least one of them. I run my normal solution twice: once on houses 0 to n − 2 (without the last), and once on houses 1 to n − 1 (without the first). The answer is the larger of the two. With a single house, I just return it, because there is nothing to leave out. "The houses are on a tree: you cannot rob a house and its direct children." What they are checking Whether you understood the two-choice idea (rob or skip), or only the list version of it. A strong answer It is the same two choices, but at each house in a tree. I visit the children first, then the house. Each house reports two numbers: the best total if I rob it (its money, plus the "skipped" totals of both children), and the best total if I skip it (the better of each child's two totals, added up). The answer is the larger of the two numbers at the root. "Tell me which houses to rob, not only the total." What they are checking Whether you can read the answer back out of a table. A strong answer I need the table, so I use Approach 1. I start at the last house. If dp[i] equals dp[i − 1] , then skipping was at least as good, so I skip house i and move to i − 1 . Otherwise I robbed it: I write down house i and jump to i − 2 . I repeat until I run out of houses. The two-number version cannot do this, because it forgets the older cells. ## Spot this pattern - You pick items from a row, and picking one blocks its neighbour. - At each item the choice is just "take it" or "skip it". - The best total up to an item depends only on the last one or two answers, so a small table, or two variables, is enough. ## Solution code ### Python ```python class Solution: def rob(self, nums): n = len(nums) if n == 1: return nums[0] dp = [0] * n # best loot using houses 0..i dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): skip = dp[i - 1] take = dp[i - 2] + nums[i] dp[i] = max(skip, take) return dp[n - 1] ``` ### Java ```java class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; int[] dp = new int[n]; // best loot using houses 0..i dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < n; i++) { int skip = dp[i - 1]; int take = dp[i - 2] + nums[i]; dp[i] = Math.max(skip, take); } return dp[n - 1]; } } ``` ### C++ ```cpp class Solution { public: int rob(vector& nums) { int n = nums.size(); if (n == 1) return nums[0]; vector dp(n); // best loot using houses 0..i dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < n; i++) { int skip = dp[i - 1]; int take = dp[i - 2] + nums[i]; dp[i] = max(skip, take); } return dp[n - 1]; } }; ``` --- From Compound Engineer (https://compoundengineer.com), visual lessons for engineers. The page above is the full interactive version.