Log inSign up
mediumLeetCodeNot Started

House Robber II

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. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system 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 = [2, 3, 2] - Output: 3 - Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses in a circle.

### Example 2 - Input: nums = [1, 2, 3, 1] - Output: 4 - Explanation: Rob house 1 (money = 1) and house 3 (money = 3), profit = 1 + 3 = 4.

### Example 3 - Input: nums = [1, 2, 3] - Output: 3

Constraints:

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

What You'll Learn

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

  • Deconstruct circular constraints into linear boundary subproblems.
  • Reuse existing linear primitives without code duplication.
  • Achieve O(n) runtime and O(1) auxiliary space.

Pattern Recognition Trigger

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

Signals to Look For:

  • Array elements arranged in a circle.
  • Non-adjacent selection constraint.
  • First and last elements cannot be chosen simultaneously.

Algorithmic Decision Tree:

  • Circular array -> split into [0..n-2] and [1..n-1].
  • Reuse linear O(1) space House Robber helper function.

Connected Patterns:

House RobberHouse Robber IIIMaximum Circular Subarray Sum

1. Recursive Suffix Exploration with First House Flag

Intuition

Recursively branch at each house, tracking whether the first house was robbed to prevent robbing house n-1.

Algorithm

  1. Define dfs(i, robbedFirst).
  2. If i >= n, return 0.
  3. If i == n - 1 and robbedFirst: cannot rob, return 0.
  4. Option 1: rob house i -> nums[i] + dfs(i + 2, robbedFirst || (i == 0)).
  5. Option 2: skip house i -> dfs(i + 1, robbedFirst).
  6. 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, bool robbedFirst, const vector<int>& nums) {
8 if (i >= (int)nums.size()) return 0;
9 if (i == (int)nums.size() - 1 && robbedFirst) return 0;
10
11 int rob = nums[i] + dfs(i + 2, robbedFirst || (i == 0), nums);
12 int skip = dfs(i + 1, robbedFirst, nums);
13 return max(rob, skip);
14}
15
16int robRec(vector<int>& nums) {
17 if (nums.empty()) return 0;
18 if (nums.size() == 1) return nums[0];
19 return dfs(0, false, nums);
20}
21
22int main() {
23 vector<int> nums = {2, 3, 2};
24 cout << "Max Robbed (Recursive): " << robRec(nums) << endl;
25 return 0;
26}

Time & Space Complexity

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

2. Two-Pass Tabulation DP

Intuition

Execute standard linear House Robber tabulation on nums[0..n-2] and nums[1..n-1].

Algorithm

  1. If nums.length == 1, return nums[0].
  2. Run linear DP on subarray nums[0..n-2] -> ans1.
  3. Run linear DP on subarray nums[1..n-1] -> ans2.
  4. Return max(ans1, ans2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int robLinear(const vector<int>& nums, int start, int end) {
8 if (start > end) return 0;
9 int len = end - start + 1;
10 if (len == 1) return nums[start];
11
12 vector<int> dp(len);
13 dp[0] = nums[start];
14 dp[1] = max(nums[start], nums[start + 1]);
15
16 for (int i = 2; i < len; i++) {
17 dp[i] = max(dp[i - 1], nums[start + i] + dp[i - 2]);
18 }
19 return dp[len - 1];
20}
21
22int robTwoPass(vector<int>& nums) {
23 int n = nums.size();
24 if (n == 0) return 0;
25 if (n == 1) return nums[0];
26 return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
27}
28
29int main() {
30 vector<int> nums = {2, 3, 2};
31 cout << "Max Robbed (Two-Pass Tabulation): " << robTwoPass(nums) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) auxiliary arrays

3. Two-Pass Rolling O(1) Space DP

Intuition

Combine the circular range split with the O(1) space rolling variables from House Robber I.

Algorithm

  1. If nums.length == 1, return nums[0].
  2. Define helper robSimple(start, end) using prev2 = 0, prev1 = 0.
  3. For i = start to end: curr = max(prev1, nums[i] + prev2); prev2 = prev1; prev1 = curr;
  4. Return max(robSimple(0, n - 2), robSimple(1, n - 1)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int robSimple(const vector<int>& nums, int start, int end) {
8 int prev2 = 0, prev1 = 0;
9 for (int i = start; i <= end; i++) {
10 int curr = max(prev1, nums[i] + prev2);
11 prev2 = prev1;
12 prev1 = curr;
13 }
14 return prev1;
15}
16
17int robOptimal(vector<int>& nums) {
18 int n = nums.size();
19 if (n == 0) return 0;
20 if (n == 1) return nums[0];
21 return max(robSimple(nums, 0, n - 2), robSimple(nums, 1, n - 1));
22}
23
24int main() {
25 vector<int> nums = {1, 2, 3, 1};
26 cout << "Max Robbed (Optimal O(1) Space): " << robOptimal(nums) << endl;
27 return 0;
28}

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 Suffix TreeO(2^n)O(n)Recursion tracking robbedFirst boolean flag.Redundant subtrees
2.Two-Pass TabulationO(n)O(n)Linear House Robber on [0..n-2] and [1..n-1].Array memory
3.Two-Pass Rolling O(1) SpaceOptimalO(n)O(1)Two linear passes with 2 scalar variables each.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting the n = 1 special check: Passing n = 1 into robSimple(0, -1) produces 0 instead of nums[0].

Pitfall 2:

Attempting to solve the circle with a single pass using modulo indexing without splitting boundaries.

Crucial Edge Cases to Validate:

  • n = 1: Must return nums[0] (cannot run [0..n-2] which would be an invalid range).
  • n = 2: Return max(nums[0], nums[1]).
  • n = 3: Return max(nums[0], nums[1], nums[2]).

Interview Tips & Best Practices

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

  1. Highlight the problem reduction technique: transforming a circular problem into two linear subproblems is a classic pattern that applies to circular buffers, gas station loops, and tree decompositions.

Quick Comprehension Check

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

1.Why does running House Robber I on [0..n-2] and [1..n-1] cover all valid robbery configurations on the circle without missing any optimal solution?

Back to DSA Sheet