House Robber
House Robber is a medium dynamic programming problem solved with the alternate selection / pick / not pick pattern.
The best approach, optimal (two variables), runs in O(n) time and O(1) space.
Below are 3 approaches in Java, from recursion (pick / not pick) up.
Problem
Houses along a street hold nums[i] money. You cannot rob two adjacent houses. Return the maximum amount you can rob.
Examples
Example 1
- Input
nums = [2, 7, 9, 3, 1]- Output
12- Why
- Rob houses 0, 2 and 4: 2 + 9 + 1.
Example 2
- Input
nums = [5, 1, 1, 5]- Output
10- Why
- Houses 0 and 3. Taking every other house is not always optimal.
Constraints
1 <= nums.length <= 100;0 <= nums[i] <= 400.- Adjacent houses cannot both be robbed.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Recursion (pick / not pick) | O(2ⁿ) | O(n) |
| Tabulation | O(n) | O(n) |
| Optimal (two variables) | O(n) | O(1) |
1Recursion (pick / not pick)
O(2ⁿ)O(n)best(i) = max(best(i - 1), nums[i] + best(i - 2)).
- Base: i < 0 → 0.
class Solution {
public int rob(int[] nums) {
return best(nums, nums.length - 1);
}
private int best(int[] a, int i) {
if (i < 0) return 0;
return Math.max(best(a, i - 1), a[i] + best(a, i - 2));
}
}2Tabulation
O(n)O(n)dp[i] = best loot from the first i houses.
- dp[0] = 0, dp[1] = nums[0].
- dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]).
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 1];
dp[1] = nums[0];
for (int i = 2; i <= n; i++) dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
return dp[n];
}
}3Optimal (two variables)
O(n)O(1)Keep the best up to the previous house and the one before it.
- prev2 = 0, prev1 = 0; cur = max(prev1, prev2 + x); shift.
class Solution {
public int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int x : nums) {
int cur = Math.max(prev1, prev2 + x);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}Edge cases to test
- One or two houses
Hints
Hint 1
At house i, either skip it (keep the best up to i - 1) or rob it (its value plus the best up to i - 2).
FAQ
What is the best time complexity for House Robber?
Optimal (two variables) runs in O(n) time and O(1) extra space.
Which pattern does House Robber use?
It is a dynamic programming problem that uses the alternate selection / pick / not pick pattern. Other problems with the same pattern: House Robber II.
Is there a brute force solution for House Robber?
Yes. Recursion (pick / not pick) takes O(2ⁿ) time and O(n) space. best(i) = max(best(i - 1), nums[i] + best(i - 2)).
Which edge cases should I test for House Robber?
One or two houses.