213. House Robber II
Asked at Databricks
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Array
Companies
1
Problem
You are robbing houses on a street, but this time the houses are arranged in a circle. So the first house and the last house are neighbors. Each house holds some money, given as an integer array nums.
You may not rob two houses that are next to each other, because the alarm would go off. Because of the circle, this also means you cannot rob both the first house and the last house.
Return the maximum total amount of money you can take without triggering the alarm.
The circle makes the ends neighbors
Constraints
- ●
1 <= nums.length <= 100 - ●
0 <= nums[i] <= 1000
Examples
nums = [2,3,2]3nums = [1,2,3,1]4nums = [1,2,3]3Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
How to Think About It
Brute force: Try all subsets of non-adjacent houses — O(2^n) time.
Observation: If you rob the first house, you cannot rob the last. If you skip the first, you might rob the last.
Split into two linear subproblems: houses [0..n-2] and houses [1..n-1].
Solve each subproblem with the standard House Robber I linear DP: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Return the maximum of both subproblems. O(n) time and O(1) space with rolling variables.
Optimal Approach
Since the houses form a circle, the first and last are adjacent and cannot both be robbed. The key insight is that any valid robbery either excludes the first house or excludes the last house. Split into two linear subproblems: rob houses [0..n-2] and rob houses [1..n-1]. Solve each with standard DP using rolling variables: prev1 = max profit ending at previous house, prev2 = profit two houses back. For each house, decide to rob it (prev2 + current) or skip it (prev1). Return the max of both subproblems. Time is O(n), space is O(1).
Split the circle into two straight lines
What Trips People Up in Real Interviews
Point out the circular constraint immediately — it changes the problem fundamentally.
Edge cases: single house → return nums[0], two houses → return max of both.
Show that splitting into two linear problems correctly covers all valid robbery combinations.
Use two variables instead of an array for O(1) space — interviewers appreciate it.
Prove correctness: any valid circular robbery either excludes house 0 or excludes house n-1.
Solution Code
O(n) timeclass Solution:
def rob(self, nums):
def robRange(start, end):
prev1, prev2 = 0, 0
for i in range(start, end + 1):
prev1, prev2 = max(prev1, prev2 + nums[i]), prev1
return prev1
n = len(nums)
if n == 1:
return nums[0]
return max(robRange(0, n - 2), robRange(1, n - 1))Frequently Asked Questions
What is the House Robber II problem?
All houses are arranged in a circle for this version of the house robber problem. You cannot rob two adjacent houses, and since the first and last houses are adjacent in the circle, you cannot rob both. Given an array of non-negative integers representing the amount of money at each house, return the maximum amount you can rob.
How do you solve House Robber II?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask House Robber II?
House Robber II is asked at Databricks. It is a medium difficulty problem.
What are common mistakes on House Robber II?
- Point out the circular constraint immediately — it changes the problem fundamentally.
- Edge cases: single house → return nums[0], two houses → return max of both.
- Show that splitting into two linear problems correctly covers all valid robbery combinations.
- Use two variables instead of an array for O(1) space — interviewers appreciate it.
- Prove correctness: any valid circular robbery either excludes house 0 or excludes house n-1.