198. House Robber - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. However, adjacent houses have security systems connected – robbing two directly adjacent houses will trigger an alarm. Given an integer array nums representing the amount of money in each house, return the maximum amount of money you can rob without alerting the police.

Example 1:
Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob the 1st and 3rd houses (money = 1 + 3 = 4). You cannot take 2nd and 3rd together because they are adjacent.
Example 2:
Input: nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob the 1st, 3rd, and 5th houses (money = 2 + 9 + 1 = 12). This is higher than any other combination (for instance, 2nd + 4th + 5th = 7 + 3 + 1 = 11).
Example 3:
Input: nums = [1, 1, 1]
Output: 2
Explanation: The best approach is to rob the 1st and 3rd houses for a total of 2. Robbing any two adjacent houses would trigger the alarm .

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 400
The sum of money is maximized by picking non-adjacent houses.
There is no circular arrangement in this problem (the first and last house are not adjacent; see House Robber II for the circular variant).

Hints

Hint 1: Think about small cases. If there is only one house, the decision is simple – rob that house. If there are two houses, you can only rob the richer house.
Hint 2: For each house, you have two choices – rob it or skip it. If you rob the current house, you must skip the next house. If you skip the current house, you move to the next one.
Hint 3: Try to formulate a relation or recurrence. Consider rob(i) as the maximum amount you can rob from houses up to index i. How does rob(i) relate to rob(i-1) and rob(i-2)?
Hint 4: Dynamic Programming can help by storing results of subproblems. You can either use memoization (top-down caching of results) or tabulation (bottom-up computation) to avoid recomputation.

Multiple Approaches

We will discuss several approaches to solve the House Robber problem, from brute force to optimized dynamic programming. Each approach will build on insights from the previous one:

Approach 1: Brute Force (Recursion)

A brute-force solution tries all possible combinations of houses to rob, enforcing the no-adjacent rule. This can be done using recursion or backtracking:

Idea: Define a recursive function robFrom(i) that returns the maximum amount you can rob starting from house index i. For each house i, you have two choices:
1. Rob house i – then you must skip house i+1 and recursively solve from house i+2.
2. Skip house i – then solve from house i+1 (move to the next house).
  Take the maximum of these two choices:
  $[text{robFrom}(i)$ = $max(\text{nums}[i]$ + $text{robFrom}(i+2)$ ,; $text{robFrom}(i+1))]$
Example (Brute Force on [1,2,3,1]):
- Start at house 0 (value 1):
  - Rob it 🡆 then you can next consider house 2.
  - Skip it 🡆 consider house 1 next.
- This forms a recursion tree exploring combinations like robbing houses {0,2}, {0,3}, {1,3}, etc., and returns the best sum (which is 4 in this case).
Problem: This approach is highly inefficient because it recomputes subproblems. Its time complexity grows exponentially (~O(2^n)) as each house branches into two possibilities. For even moderate n (number of houses), this becomes infeasible. It's useful for understanding the problem, but we need optimization to handle up to 100 houses.

Approach 2: Dynamic Programming with Memoization (Top-Down)

To eliminate the repeated calculations in the brute force approach, we can use memoization. Memoization stores the results of subproblems (here, the results of robFrom(i) for each index i) so that each subproblem is solved only once.

Idea: Use the same recursive strategy as brute force, but maintain a cache (dictionary or array) memo where memo[i] = result of robFrom(i). If robFrom(i) has been computed before, use the cached value instead of recomputing it.
Steps:
1. If i >= len(nums), there are no houses left to examine, so return 0.
2. If we have solved robFrom(i) before (i.e., memo[i] exists), return memo[i].
3. Otherwise, compute it recursively as:
  $[text{memo}[i]$ = $max(text{nums}[i]$ + $text{robFrom}(i+2)$ ,; text{robFrom (i+1))]
4. Return memo[i].
Example (Top-Down on [2,7,9,3,1]):
- Start robFrom(0): needs max of (rob house0 + robFrom(2)) vs (skip house0 + robFrom(1)).
- It will compute robFrom(2) and robFrom(1). These in turn compute further subproblems. With memoization, each index is solved once. For instance, robFrom(2) (houses [9,3,1]) might recursively compute robFrom(4) and robFrom(3), then store and reuse those results.
- The recursion with caching ensures we explore each house index at most once, making it efficient.
Complexity: Top-down with memoization runs in O(n) time and uses O(n) space for the recursion stack and memo table, where n is the number of houses. This is a big improvement over brute force.

Approach 3: Dynamic Programming with Tabulation (Bottom-Up)

Another way to use dynamic programming is tabulation, a bottom-up approach. We directly build the solution for the first i houses, for all i from 0 up to n-1, using the recurrence relation derived from our reasoning.

Idea: Create a DP array dp of length n, where dp[i] represents the maximum amount of money that can be robbed up to (and including) the i-th house. We can formulate:
- dp[0] = nums[0] (if there's only one house, rob it).
- dp[1] = max(nums[0], nums[1]) (for two houses, rob the richer one).
- For i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
  - This means for house i, we either skip it (then the best is whatever we had up to house i-1), or rob it (then add this house's money to the best up to house i- 2】. We choose the better of these two options for dp[i].
Example (Bottom-Up on [2, 7, 9, 3, 1]):
Let's build the dp array step by step:
- dp[0] = 2 (only first house)
- dp[1] = max(2, 7) = 7 (best of first two houses)
- dp[2] = max(dp[1], dp[0] + 9) = max(7, 2+9) = 11 (rob houses 1 and 3 for 11)
- dp[3] = max(dp[2], dp[1] + 3) = max(11, 7+3) = 11 (best is still 11, either rob houses 1 & 3 or 2 & 4)
- dp[4] = max(dp[3], dp[2] + 1) = max(11, 11+1) = 12 (rob houses 1, 3, and 5 for 12)
- The last entry dp[4] is 12, which is the answer.
In this way, we fill the table in one pass. Each dp[i] calculation uses the results of two previously solved subproblems (dp[i-1] and dp[i-2]). This ensures an efficient computation.
Analysis: The bottom-up approach also runs in O(n) time, and it uses O(n) space for the dp array. Given the constraints (at most 100 houses), using an array of size 100 is not a problem at all. This approach is straightforward and easy to implement.

Approach 4: Optimized Space Dynamic Programming (Two Variables)

We can observe that to compute dp[i], we only need the values of dp[i-1] and dp[i-2]. We don't actually need to store the entire dp array of size n if we're only going to reuse the last two results at each step. We can optimize space by keeping track of just two variables as we iterate through the houses:

Idea: Maintain two variables to represent the best loot up to the previous house and the house before that. Let's call them prevOne (the best up to i-1) and prevTwo (the best up to i-2). For each house value num in the array, update these as:
- current = max(prevOne, prevTwo + num) – this mirrors the relation max(dp[i-1], dp[i-2] + num).
- Then set prevTwo = prevOne and prevOne = current to move the window forward.
This way, as we go through the list, prevOne always holds the best solution up to the current house, and prevTwo holds the best up to the previous house (one index behind).
Why it works: It's essentially the same recurrence, but we overwrite and recycle variables instead of using an array. By the end of the iteration, prevOne (or current) will hold the answer for the full list.
Efficiency: This approach still examines each house once (O(n) time) but only uses a constant amount of extra space (O(1) space), making it optimal in terms of both time and memory. We’ll walk through an example of this approach in detail in the next section.

Code Implementations

Below are implementations of the optimized dynamic programming solution in both Python and Java. The logic can be easily adapted for the other approaches as well, but we demonstrate the most efficient solution here.

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Note: In the Java code, we use a single class HouseRobber containing the solution method and a main method for demonstration. This avoids any issues with multiple public classes. The outputs printed correspond to the example test cases.

Complexity Analysis

Let's analyze the time and space complexity of each approach:

Brute Force (Recursive):
- Time Complexity: O(2^n). Each house leads to two recursive calls (rob or skip), resulting in a binary recursion tree. This exponential growth makes it impractical for large n.
- Space Complexity: O(n) due to recursion call stack in the worst case (depth of recursion can go up to n in the skip path).
Dynamic Programming – Memoization (Top-Down):
- Time Complexity: O(n). Each house index is computed at most once thanks to caching. The recurrence relation robFrom(i) does constant work aside from recursive calls.
- Space Complexity: O(n). We use a memo table of size n to store results. Additionally, recursion stack depth is at most n, which is O(n) space in the worst case.
Dynamic Programming – Tabulation (Bottom-Up):
- Time Complexity: O(n). We fill the dp array with n entries, doing O(1) work for each via the recurrenc 8】
- Space Complexity: O(n). We allocate an array of size n for dp. This is linear in the number of houses. For n up to 100 (per constraints), this is very smal 6】
Optimized DP (Constant Space):
- Time Complexity: O(n). We still iterate through the list of houses once, doing a constant amount of work (a couple of calculations and assignments) for each house.
- Space Complexity: O(1). We use only a fixed number of variables (prevTwo, prevOne, and current) to keep track of the needed state. This is a constant space solution, apart from the input array itself.

All efficient approaches (memoization, tabulation, optimized) achieve linear time complexity. The optimized approach saves space by not using an extra array.

Step-by-Step Walkthrough of Optimized Solution

Let's walk through the space-optimized DP solution with a concrete example to see how it works. Consider the input array: nums = [2, 7, 9, 3, 1] (the same as Example 2). We will trace the values of our two tracking variables (prevTwo and prevOne) and the decision at each step:

Initialization: Before processing any houses, prevTwo = 0 and prevOne = 0 (no money robbed yet).

Now iterate through each house:

House 1 (value = 2):
- If we rob this house, since prevTwo represents the best up to two houses ago (which is 0 at start), total = prevTwo + 2 = 0 + 2 = 2.
- If we skip this house, total = prevOne = 0 (best up to previous house, which is none).
- Decision: Take the maximum of these two choices, which is 2.
- Update the trackers: prevTwo becomes the old prevOne (0), and prevOne becomes the new max (2).
- State after House 1: prevTwo = 0, prevOne = 2 (Maximum so far = 2).
House 2 (value = 7):
- If we rob this house, total = prevTwo + 7 = 0 + 7 = 7 (we add 7 to the best up to house 0, since we can't take house 1 if we take house 2).
- If we skip this house, total = prevOne = 2 (carry forward the best from house 1).
- Decision: Max is 7 (robbing this house is better).
- Update trackers: prevTwo = 2 (old prevOne), prevOne = 7 (new max).
- State after House 2: prevTwo = 2, prevOne = 7 (Maximum so far = 7).
House 3 (value = 9):
- If we rob this house, total = prevTwo + 9 = 2 + 9 = 11 (add 9 to best up to house 1).
- If we skip, total = prevOne = 7 (best up to house 2).
- Decision: Max is 11 (robbing house 3 yields 11, which is better than skipping it).
- Update trackers: prevTwo = 7, prevOne = 11.
- State after House 3: prevTwo = 7, prevOne = 11 (Maximum so far = 11).
House 4 (value = 3):
- If we rob this house, total = prevTwo + 3 = 7 + 3 = 10 (add 3 to best up to house 2).
- If we skip, total = prevOne = 11 (best up to house 3).
- Decision: Max is 11 (skipping house 4 is better, because robbing it would drop the total to 10).
- Update trackers: prevTwo = 11, prevOne = 11 (no change in max because we skipped robbing house 4).
- State after House 4: prevTwo = 11, prevOne = 11 (Maximum so far = 11).
House 5 (value = 1):
- If we rob this house, total = prevTwo + 1 = 11 + 1 = 12 (add 1 to best up to house 3).
- If we skip, total = prevOne = 11 (best up to house 4).
- Decision: Max is 12 (robbing house 5 gives 12, which is better than 11).
- Update trackers: prevTwo = 11, prevOne = 12.
- State after House 5: prevTwo = 11, prevOne = 12 (Maximum so far = 12).

After processing all houses, prevOne = 12 is the maximum amount we can rob without alerting the police. This matches our expected result for [2,7,9,3,1]. Notice how at each step, the decision to rob or skip a house is made by comparing (prevTwo + current_house_value) vs. prevOne, which exactly implements the relation max(dp[i-2] + nums[i], dp[i-1]).

Visualization of choices: At the end of the process for [2,7,9,3,1], the houses contributing to the maximum loot are the 1st, 3rd, and 5th houses (values 2 + 9 + 1 = 12). The algorithm arrived at this by always considering the best combination up to two houses back plus current house versus the best up to the previous house.

Common Mistakes & Edge Cases

Off-by-One Errors: Forgetting to handle the first couple of houses properly is common. Always initialize the base cases correctly. For instance, if there is only one house, return its value; for two houses, return the max of the two. Our code handles this implicitly by initialization, but if you use an array dp, ensure dp[1] = max(nums[0], nums[1]) is set correctly.
Greedy Pitfall: A common incorrect approach is to greedily pick every alternate house (like always skip one house after robbing one). This doesn’t always yield the optimal result. For example, in [2, 1, 1, 2], a greedy approach might rob house 1 (money=2), skip house 2, rob house 3 (money=1), skip house 4 – yielding 3; but the optimal solution is to rob house 1 and house 4 for a total of 4. The dynamic programming approach correctly finds the optimal solution by considering all possibilities at each step.
Not Handling Small Inputs: Ensure your solution handles edge cases such as:
- One house: e.g. [5] should return 5.
- Two houses: e.g. [10, 40] should return 40 (take the larger of the two).
- All houses zero: e.g. [0,0,0] should return 0 (robbing nothing yields 0, which is fine, and any combination is 0).
- Our implementations consider these cases. For instance, if the input list is empty (though the problem says at least 1 house), we return 0. If it has one element, the loop will simply return that element as prevOne. If it has two, the loop logic will end up taking the max of them.
Updating Variables Incorrectly: If implementing the space-optimized approach, be careful to use a temporary variable or update in the correct order. For example, updating prevTwo after computing current (as shown) is important. If you naively do prevOne = max(prevOne, prevTwo + num) and then prevTwo = prevOne in the wrong order, you will lose information. A common mistake is not using a temp variable current and doing updates in a way that uses already updated values.

Alternative Variations

The "House Robber" problem is a classic dynamic programming problem, and its technique can be adapted to many variations:

House Robber II (LeetCode 213): This is a variation where houses are arranged in a circle (the first and last house are also adjacent). You cannot rob both the first and last house. The problem can be solved by splitting it into two linear subproblems: (1) rob houses 1 to n-1, and (2) rob houses 2 to n, then take the maximum of the two results. This works because either you rob the first house or you don't – if you do, you can't rob the last, and vice versa. The core logic of skipping adjacent houses remains the same dynamic programming approach in each case.
House Robber III (LeetCode 337): In this variation, houses are arranged in a binary tree shape instead of a line. You can’t rob two directly connected houses (parent-child in the tree). This is solved with a tree DFS that returns two values for each node: the max if you rob that node (then you can’t rob children), and the max if you skip that node (then you take the best from children). The recurrence is similar in spirit, but implemented via post-order traversal of the tree.
Maximum Sum of Non-Adjacent Elements: This is a generalized version of the problem often asked in interviews (sometimes called the "max sum with no two adjacent" problem). There’s no house-robbing story, but the task is the same: given an array of numbers, pick the maximum sum of elements such that no two picked elements are adjacent. The solution is identical to the House Robber DP solution. Many coding challenges use this formulation.
“Delete and Earn” (LeetCode 740): This problem transforms into a House Robber scenario. You are given an array of numbers, and if you take (delete and earn) a number, you gain its value but also must delete any occurrences of adjacent values (e.g., if you take value 3, you can't take 2 or 4 because those become "adjacent" in value). By preprocessing, this can be converted into an array where index represents the value and you accumulate total points for each value – then you basically solve it like a house robber problem on this value-index array. It’s a clever twist but boils down to the same DP recurrence.
Variants with Weight Limits or Other Constraints: Some variations might add additional constraints (like a limit on total weight or skipping more than one house, etc.). But generally, as long as the main restriction is "no two adjacent picks," the dynamic programming strategy remains applicable.

To strengthen your understanding of this pattern, you can practice the following related LeetCode problems:

198. House Robber – (The problem we just solved.)
213. House Robber II – (Medium) Houses in a circle, requires considering two ranges as explained above.
337. House Robber III – (Medium) Houses represented as nodes of a binary tree, solved via tree DP.
740. Delete and Earn – (Medium) Convert to a take-and-skip (house robber) problem on values.
1143. Longest Common Subsequence – (Different context, but practices DP thinking, constructing solutions from subproblems.)
55. Jump Game – (Dynamic programming / greedy problem which also can be approached with similar thinking of reachable indices, though not a robbery scenario).