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, Python, C++ and JavaScript, 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.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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 code in Java, Python, C++ and JavaScript.
| 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));
}
}class Solution:
def rob(self, nums: List[int]) -> int:
return self.best(nums, len(nums) - 1)
def best(self, a: List[int], i: int) -> int:
if i < 0:
return 0
return max(self.best(a, i - 1), a[i] + self.best(a, i - 2))class Solution {
public:
int rob(vector<int>& nums) {
return best(nums, nums.size() - 1);
}
private:
int best(vector<int>& a, int i) {
if (i < 0) return 0;
return max(best(a, i - 1), a[i] + best(a, i - 2));
}
};function rob(nums) {
function best(a, i) {
if (i < 0) return 0;
return Math.max(best(a, i - 1), a[i] + best(a, i - 2));
}
return best(nums, nums.length - 1);
}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];
}
}class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * (n + 1)
dp[1] = nums[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
return dp[n]class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n + 1, 0);
dp[1] = nums[0];
for (int i = 2; i <= n; i++) dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
return dp[n];
}
};function rob(nums) {
const n = nums.length;
const dp = new Array(n + 1).fill(0);
dp[1] = nums[0];
for (let 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;
}
}class Solution:
def rob(self, nums: List[int]) -> int:
prev2, prev1 = 0, 0
for x in nums:
cur = max(prev1, prev2 + x)
prev2 = prev1
prev1 = cur
return prev1class Solution {
public:
int rob(vector<int>& nums) {
int prev2 = 0, prev1 = 0;
for (int x : nums) {
int cur = max(prev1, prev2 + x);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
};function rob(nums) {
let prev2 = 0, prev1 = 0;
for (const x of nums) {
const 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.