Approach Summary
At each house: either rob it (prev_prev + current) or skip it (prev). Track two previous values.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: 1D Dynamic Programming Tabulation | O(n) | O(n) | Allocate array dp where dp[i] is max loot possible from first i houses. |
| 2 Approach 2: Two-Variable Space Optimization (Optimal) | O(n) | O(1) | Track only the maximum loot from the preceding two houses to achieve O(1) space. |
Step 1: Baseline
Approach 1: 1D Dynamic Programming Tabulation
Time: O(n)
Space: O(n)
Create array dp of length n + 1. Base cases: dp[0] = 0, dp[1] = nums[0]. For i from 2 to n: dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]). The answer is stored in dp[n].
Approach 1: 1D Dynamic Programming Tabulation Implementation
Approach 1: 1D Dynamic Programming Tabulation
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n + 1];
dp[0] = 0;
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 {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n + 1, 0);
dp[0] = 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];
}
};class Solution:
def rob(self, nums: list[int]) -> int:
n = len(nums)
if n == 0:
return 0
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]function rob(nums) {
const n = nums.length;
if (n === 0) return 0;
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];
} Step 2: Most Optimized
Approach 2: Two-Variable Space Optimization (Optimal)
Time: O(n)
Space: O(1)
Because dp[i] relies exclusively on dp[i - 1] and dp[i - 2], store them in variables prev1 and prev2. As we iterate through each house, update prev1 = max(prev1, prev2 + num) and shift prev2 = old_prev1. This eliminates array allocations entirely.
Approach 2: Two-Variable Space Optimization (Optimal) Implementation
Approach 2: Two-Variable Space Optimization (Optimal)
class Solution {
public int rob(int[] nums) {
int prev1 = 0;
int prev2 = 0;
for (int i = 0; i < nums.length; i++) {
int temp = prev1;
prev1 = Math.max(prev1, prev2 + nums[i]);
prev2 = temp;
}
return prev1;
}
}class Solution {
public:
int rob(vector<int>& nums) {
int prev1 = 0;
int prev2 = 0;
for (int i = 0; i < nums.size(); i++) {
int temp = prev1;
prev1 = max(prev1, prev2 + nums[i]);
prev2 = temp;
}
return prev1;
}
};class Solution:
def rob(self, nums: list[int]) -> int:
prev1, prev2 = 0, 0
for num in nums:
temp = prev1
prev1 = max(prev1, prev2 + num)
prev2 = temp
return prev1function rob(nums) {
let prev1 = 0;
let prev2 = 0;
for (let i = 0; i < nums.length; i++) {
const temp = prev1;
prev1 = Math.max(prev1, prev2 + nums[i]);
prev2 = temp;
}
return prev1;
}Edge Cases to Watch
- Empty array (returns 0)
- Single house (returns nums[0])
- Two houses (returns max(nums[0], nums[1]))
- All houses have identical values (robs every alternate house)
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- Cannot take adjacent elements
- Max sum with gap-1 constraint
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Array DP
Frequently Asked Questions
What is the optimal time and space complexity for House Robber?
The optimal solution for House Robber achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n) as we scan the array in a single linear pass. Space complexity is O(1) when using two running variables.
How do I identify that House Robber requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Cannot take adjacent elements; Max sum with gap-1 constraint. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in House Robber?
Essential edge cases to verify include: Empty array (returns 0); Single house (returns nums[0]); Two houses (returns max(nums[0], nums[1])); All houses have identical values (robs every alternate house). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask House Robber?
House Robber is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Airbnb.