Log inSign up
mediumLeetCodeNot Started

House Robber

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

### Example 1 - Input: nums = [1, 2, 3, 1] - Output: 4 - Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

### Example 2 - Input: nums = [2, 7, 9, 3, 1] - Output: 12 - Explanation: Rob house 1 (money = 2), house 3 (money = 9), and house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate the classic non-adjacent choice recurrence.
  • Understand why this is isomorphic to Fibonacci with weighted choices.
  • Optimize to O(1) space using rolling variables.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Linear array where choosing element i forbids choosing element i - 1 or i + 1.
  • Maximizing total profit or value under adjacency constraints.

Algorithmic Decision Tree:

  • Include current -> add to state from 2 steps back.
  • Exclude current -> inherit state from 1 step back.

Connected Patterns:

House Robber IIHouse Robber IIIDelete and Earn

1. Recursive Decision Tree

Intuition

For each house, branch into either robbing it and advancing by 2, or skipping it and advancing by 1.

Algorithm

  1. Define dfs(i).
  2. If i >= nums.length, return 0.
  3. Option 1: rob house i -> nums[i] + dfs(i + 2).
  4. Option 2: skip house i -> dfs(i + 1).
  5. Return max(Option 1, Option 2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int dfs(int i, const vector<int>& nums) {
8 if (i >= (int)nums.size()) return 0;
9 int rob = nums[i] + dfs(i + 2, nums);
10 int skip = dfs(i + 1, nums);
11 return max(rob, skip);
12}
13
14int robRec(vector<int>& nums) {
15 return dfs(0, nums);
16}
17
18int main() {
19 vector<int> nums = {2, 7, 9, 3, 1};
20 cout << "Max Robbed (Recursive): " << robRec(nums) << endl;
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Dynamic Programming Tabulation

Intuition

Build an array dp of size n where dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]).

Algorithm

  1. If nums.length == 1, return nums[0].
  2. Create array dp of size n.
  3. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
  4. For i = 2 to n - 1:
  5. dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]).
  6. Return dp[n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int robTab(vector<int>& nums) {
8 int n = nums.size();
9 if (n == 0) return 0;
10 if (n == 1) return nums[0];
11
12 vector<int> dp(n);
13 dp[0] = nums[0];
14 dp[1] = max(nums[0], nums[1]);
15
16 for (int i = 2; i < n; i++) {
17 dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
18 }
19 return dp[n - 1];
20}
21
22int main() {
23 vector<int> nums = {2, 7, 9, 3, 1};
24 cout << "Max Robbed (Tabulation): " << robTab(nums) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) array space

3. O(1) Space Rolling Variables

Intuition

Maintain two scalars prev2 and prev1 tracking max profit up to house i-2 and house i-1.

Algorithm

  1. If nums.empty(), return 0.
  2. prev2 = 0, prev1 = 0.
  3. For each num in nums:
  4. curr = max(prev1, num + prev2)
  5. prev2 = prev1
  6. prev1 = curr
  7. Return prev1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int robOptimal(vector<int>& nums) {
8 int prev2 = 0, prev1 = 0;
9 for (int num : nums) {
10 int curr = max(prev1, num + prev2);
11 prev2 = prev1;
12 prev1 = curr;
13 }
14 return prev1;
15}
16
17int main() {
18 vector<int> nums = {2, 7, 9, 3, 1};
19 cout << "Max Robbed (Optimal O(1) Space): " << robOptimal(nums) << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive TreeO(2^n)O(n)Exhaustive branching over rob vs skip.Redundant subproblems
2.DP TabulationO(n)O(n)dp array tracking prefix max amounts.Array memory
3.Rolling VariablesOptimalO(n)O(1)prev2 and prev1 scalar updates.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Robbing every other house blindly (e.g. [2, 1, 1, 2] -> optimal is 2 + 2 = 4 by skipping two consecutive houses).

Pitfall 2:

Confusing House Robber (linear street) with House Robber II (circular street).

Crucial Edge Cases to Validate:

  • Single house: Return nums[0].
  • Two houses: Return max(nums[0], nums[1]).
  • All zero money: Return 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Point out that this pattern directly generalizes to 'Delete and Earn' and 'House Robber II'.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does initializing prev2 = 0 and prev1 = 0 correctly handle any array of length >= 1 without needing explicit special base case checks?

Back to DSA Sheet