House Robber II
Problem Statement
The houses are arranged in a circle, so the first and last houses are also adjacent. Each house contains money, and robbing adjacent houses triggers the alarm. Given nums, return the maximum amount you can rob without robbing adjacent houses.
Input
An integer array nums, where the first and last entries are neighbouring houses because the street is circular.
Output
An integer: the maximum money that can be robbed without choosing adjacent circular neighbours.
Constraints
- •
1 <= nums.length <= 100 - •
0 <= nums[i] <= 1000
Examples
Example 1
nums = [2,3,2]
3Example 2
nums = [1,2,3,1]
4Example 3
nums = [1,2,3]
3Learning Objectives
- Break a circular adjacency constraint into two linear subproblems.
- Reuse the House Robber recurrence on a selected inclusive range.
- Handle the single-house edge case before splitting ranges.
- Explain why excluding first or excluding last covers every valid solution.
Intuition
The only new conflict is between the first and last houses. A valid robbery plan cannot include both. Therefore every valid plan belongs to one of two groups: plans that exclude the first house, or plans that exclude the last house. Those two groups cover all possibilities.
Once one endpoint is excluded, the remaining houses form a normal line. So we do not need a new recurrence. We run the linear House Robber helper twice, once on houses 0 through n - 2 and once on houses 1 through n - 1, then take the better result.
Common mistakes
- ×Running the original House Robber recurrence on the whole array and accidentally allowing both endpoints.
- ×Excluding both the first and last houses, which is too restrictive.
- ×Forgetting the single-house case, where both split ranges would be invalid or empty.
- ×Trying to track circular state inside one complicated DP instead of reducing to two clean linear runs.
State Definition
For a linear range start...end, let dp[i] be the maximum money that can be robbed from that range up to house i without robbing adjacent houses. The circular answer is max(linear(0, n - 2), linear(1, n - 1)).
State Transition
Inside either linear range, the recurrence is the same as House Robber:
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]).
The circular base case is n = 1, where the answer is nums[0]. For longer arrays, one linear pass excludes the last house and the other excludes the first house, so the endpoint conflict disappears.
Solutions
Solution: Two linear robber passes
Split the circle into two lines: one range that cannot use the last house, and one range that cannot use the first house. Reuse an O(1)-space linear robber helper for both ranges.
Step-by-step
- If there is only one house, return its value immediately.
- Compute the best linear robbery from index 0 through n - 2.
- Compute the best linear robbery from index 1 through n - 1.
- Return the maximum of the two results because every valid circular plan excludes at least one endpoint.
O(n)
O(1)
Two linear passes over overlapping ranges still take linear time and constant extra space.
Java implementation
Dry Run
Sample input
nums = [1,2,3,1]. Run the linear helper twice: exclude the last house, then exclude the first house.
| pass | index | house value | twoHousesBack before | oneHouseBack before | current best |
|---|---|---|---|---|---|
| exclude last | 0 | 1 | 0 | 0 | 1 |
| exclude last | 1 | 2 | 0 | 1 | 2 |
| exclude last | 2 | 3 | 1 | 2 | 4 |
| exclude first | 1 | 2 | 0 | 0 | 2 |
| exclude first | 2 | 3 | 0 | 2 | 3 |
| exclude first | 3 | 1 | 2 | 3 | 3 |
The best range excluding the last house is 4. The best range excluding the first house is 3. Taking the maximum gives 4.
Complexity Analysis
The circle is handled by two O(n) linear passes, not by a new higher-dimensional DP table.
Two linear robber passes
O(n)
O(1)
Two linear passes over overlapping ranges still take linear time and constant extra space.
Interview Tips
The key interview move is the reduction: first and last cannot both be chosen, so solve one case without the first and one case without the last. After that, reuse the original House Robber recurrence. Mention the n = 1 edge case before forming ranges.
Likely follow-ups
- What if houses are arranged in a binary tree instead of a circle?
- How would you return which houses were robbed for the chosen circular plan?
- What if at least one house must be robbed even when all values are zero?
- How would the solution change if houses within distance 2 could not both be robbed?
Similar Problems
Key Takeaways
- A circular endpoint conflict can often be split into exclude-first and exclude-last cases.
- After removing one endpoint, the original linear DP recurrence applies unchanged.
- Handle **n = 1** before creating the two ranges.
- Two linear passes are still O(n) time and O(1) space.