Approach Summary
Houses form a circle so first and last are adjacent. Run House Robber on [0..n-2] and [1..n-1], return the max.
Practice Mode
3 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: Two-Pass Linear DP on Decoupled Ranges (Optimal) | O(n) | O(1) | Split circular array into two linear sub-ranges: [0...n-2] and [1...n-1], returning max of both. |
| 2 Approach 2: Top-Down Recursion with Memoization (Baseline) | O(n) | O(n) | Recursive memoized exploration of houses [0..n-2] and [1..n-1] to break the circle. |
| 3 Approach 2: Top-Down Recursion with Memoization (Baseline) | O(n) | O(n) | Recursive memoized exploration of houses [0..n-2] and [1..n-1] to break the circle. |
Step 1: Baseline
Approach 1: Two-Pass Linear DP on Decoupled Ranges (Optimal)
Time: O(n)
Space: O(1)
Because house 0 and house n - 1 cannot both be robbed, we break the cycle by analyzing two mutually exclusive scenarios: 1) Exclude house n - 1 and solve for [0...n - 2]. 2) Exclude house 0 and solve for [1...n - 1]. Each range is a standard House Robber I problem solved in O(n) time and O(1) space. The maximum of both results covers all legal robbing combinations.
Approach 1: Two-Pass Linear DP on Decoupled Ranges (Optimal) Implementation
Approach 1: Two-Pass Linear DP on Decoupled Ranges (Optimal)
class Solution {
int robHelper(int nums[], int start, int n) {
int prev1 = 0;
int prev2 = 0;
for (int i = start; i < n; i++) {
int temp = prev1;
prev1 = Math.max(prev1, prev2 + nums[i]);
prev2 = temp;
}
return prev1;
}
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
else if (n == 1) return nums[0];
int robFirst = robHelper(nums, 0, n - 1);
int robLast = robHelper(nums, 1, n);
return Math.max(robFirst, robLast);
}
}class Solution {
public:
int robHelper(vector<int>& nums, int start, int n) {
int prev1 = 0;
int prev2 = 0;
for (int i = start; i < n; i++) {
int temp = prev1;
prev1 = max(prev1, prev2 + nums[i]);
prev2 = temp;
}
return prev1;
}
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
else if (n == 1) return nums[0];
int robFirst = robHelper(nums, 0, n - 1);
int robLast = robHelper(nums, 1, n);
return max(robFirst, robLast);
}
};class Solution:
def rob(self, nums: list[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
def rob_range(start, end):
prev1, prev2 = 0, 0
for i in range(start, end):
temp = prev1
prev1 = max(prev1, prev2 + nums[i])
prev2 = temp
return prev1
return max(rob_range(0, n - 1), rob_range(1, n))function rob(nums) {
const n = nums.length;
if (n === 0) return 0;
if (n === 1) return nums[0];
function robHelper(start, end) {
let prev1 = 0;
let prev2 = 0;
for (let i = start; i < end; i++) {
const temp = prev1;
prev1 = Math.max(prev1, prev2 + nums[i]);
prev2 = temp;
}
return prev1;
}
return Math.max(robHelper(0, n - 1), robHelper(1, n));
} Step 2
Approach 2: Top-Down Recursion with Memoization (Baseline)
Time: O(n)
Space: O(n)
Uses two separate memoization tables to solve the linear subproblems: robbing from index 0 to n-2 (excluding the last house) and from index 1 to n-1 (excluding the first house). The maximum of both branches gives the optimal solution.
Approach 2: Top-Down Recursion with Memoization (Baseline) Implementation
Approach 2: Top-Down Recursion with Memoization (Baseline)
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1));
}
private int robRange(int[] nums, int start, int end) {
int[] memo = new int[nums.length];
Arrays.fill(memo, -1);
return dfs(nums, start, end, memo);
}
private int dfs(int[] nums, int i, int end, int[] memo) {
if (i > end) return 0;
if (memo[i] != -1) return memo[i];
return memo[i] = Math.max(nums[i] + dfs(nums, i + 2, end, memo), dfs(nums, i + 1, end, memo));
}
}class Solution {
int dfs(vector<int>& nums, int i, int end, vector<int>& memo) {
if (i > end) return 0;
if (memo[i] != -1) return memo[i];
return memo[i] = max(nums[i] + dfs(nums, i + 2, end, memo), dfs(nums, i + 1, end, memo));
}
int robRange(vector<int>& nums, int start, int end) {
vector<int> memo(nums.size(), -1);
return dfs(nums, start, end, memo);
}
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
return max(robRange(nums, 0, nums.size() - 2), robRange(nums, 1, nums.size() - 1));
}
};class Solution:
def rob(self, nums: list[int]) -> int:
if len(nums) == 1: return nums[0]
def rob_memo(sub):
memo = {}
def dfs(i):
if i >= len(sub): return 0
if i in memo: return memo[i]
memo[i] = max(sub[i] + dfs(i + 2), dfs(i + 1))
return memo[i]
return dfs(0)
return max(rob_memo(nums[:-1]), rob_memo(nums[1:]))function rob(nums) {
if (nums.length === 1) return nums[0];
function robMemo(sub) {
const memo = new Map();
function dfs(i) {
if (i >= sub.length) return 0;
if (memo.has(i)) return memo.get(i);
const res = Math.max(sub[i] + dfs(i + 2), dfs(i + 1));
memo.set(i, res);
return res;
}
return dfs(0);
}
return Math.max(robMemo(nums.slice(0, -1)), robMemo(nums.slice(1)));
} Step 2: Most Optimized
Approach 2: Top-Down Recursion with Memoization (Baseline)
Time: O(n)
Space: O(n)
Uses two separate memoization tables to solve the linear subproblems: robbing from index 0 to n-2 (excluding the last house) and from index 1 to n-1 (excluding the first house). The maximum of both branches gives the optimal solution.
Approach 2: Top-Down Recursion with Memoization (Baseline) Implementation
Approach 2: Top-Down Recursion with Memoization (Baseline)
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1));
}
private int robRange(int[] nums, int start, int end) {
int[] memo = new int[nums.length];
Arrays.fill(memo, -1);
return dfs(nums, start, end, memo);
}
private int dfs(int[] nums, int i, int end, int[] memo) {
if (i > end) return 0;
if (memo[i] != -1) return memo[i];
return memo[i] = Math.max(nums[i] + dfs(nums, i + 2, end, memo), dfs(nums, i + 1, end, memo));
}
}class Solution {
int dfs(vector<int>& nums, int i, int end, vector<int>& memo) {
if (i > end) return 0;
if (memo[i] != -1) return memo[i];
return memo[i] = max(nums[i] + dfs(nums, i + 2, end, memo), dfs(nums, i + 1, end, memo));
}
int robRange(vector<int>& nums, int start, int end) {
vector<int> memo(nums.size(), -1);
return dfs(nums, start, end, memo);
}
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
return max(robRange(nums, 0, nums.size() - 2), robRange(nums, 1, nums.size() - 1));
}
};class Solution:
def rob(self, nums: list[int]) -> int:
if len(nums) == 1: return nums[0]
def rob_memo(sub):
memo = {}
def dfs(i):
if i >= len(sub): return 0
if i in memo: return memo[i]
memo[i] = max(sub[i] + dfs(i + 2), dfs(i + 1))
return memo[i]
return dfs(0)
return max(rob_memo(nums[:-1]), rob_memo(nums[1:]))function rob(nums) {
if (nums.length === 1) return nums[0];
function robMemo(sub) {
const memo = new Map();
function dfs(i) {
if (i >= sub.length) return 0;
if (memo.has(i)) return memo.get(i);
const res = Math.max(sub[i] + dfs(i + 2), dfs(i + 1));
memo.set(i, res);
return res;
}
return dfs(0);
}
return Math.max(robMemo(nums.slice(0, -1)), robMemo(nums.slice(1)));
}Edge Cases to Watch
- Single house (e.g. nums = [5]; returns nums[0] immediately)
- Two houses (returns max(nums[0], nums[1]))
- Three houses (returns max(nums[0], nums[1], nums[2]))
- All houses have 0 value
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
- Circular arrangement means first and last conflict
- Run linear House Robber twice on overlapping ranges
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Array Dynamic Programming
Frequently Asked Questions
What is the optimal time and space complexity for House Robber II?
The optimal solution for House Robber II achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n) because we run two linear passes of House Robber I over slices of size n - 1. Space complexity is O(1) because each pass uses only two scalar variables.
How do I identify that House Robber II requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Circular arrangement means first and last conflict; Run linear House Robber twice on overlapping ranges. 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 II?
Essential edge cases to verify include: Single house (e.g. nums = [5]; returns nums[0] immediately); Two houses (returns max(nums[0], nums[1])); Three houses (returns max(nums[0], nums[1], nums[2])); All houses have 0 value. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask House Robber II?
House Robber II is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Airbnb.