House Robber II
Problem
Given a list of non-negative integers representing the amount of money of each house arranged in a circle, return the maximum amount of money you can rob without robbing two adjacent houses.
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 1000
Example
nums = [2,3,2]3The houses are arranged in a circle: house 0 with 2, house 1 with 3, and house 2 with 2. Robbing house 0 and house 2 is not allowed because they are adjacent in the circle. The optimal choice is to rob house 1 only, yielding 3. The algorithm solves this by considering two linear cases: robbing houses from index 0 to n-2, and robbing houses from index 1 to n-1, then taking the maximum of these two results.
Approach
Straightforward Solution
A brute-force approach would try all subsets of houses excluding adjacent ones, but the circular constraint complicates this, making naive recursion or backtracking exponential and inefficient.
Core Observation
The circular adjacency constraint means the first and last houses cannot both be robbed. This breaks the straightforward linear dynamic programming approach used in the simpler House Robber problem.
Path to Optimal
PreviewThe key insight is to transform the circular problem into two linear subproblems by excluding either the first or the last house. Each subproblem can be solved using the classic linear House Robber DP approach…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewDefine a helper function that computes the maximum robbery amount for a linear list of houses using DP with memoization. Then, compute the maximum for nums excluding the last house and nums excluding the first house, and return the maximum of these two results…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each linear subproblem is solved with memoized recursion that visits each house index once, resulting in O(n) time. Since two subproblems are solved, total time remains O(n).
Space
O(n)
Memoization dictionaries store results for each house index in the linear subproblems, requiring O(n) auxiliary space. The recursion stack depth is also O(n) in the worst case.
Pattern Spotlight
Dynamic Programming (Linear Subproblem Decomposition)
When a circular dependency prevents direct DP application, break the problem into multiple linear subproblems by excluding conflicting elements, solve each independently with DP, and combine results to respect the original constraints.
Solution
| 1 | class Solution:
|
| 2 | def rob(self, nums: list[int]) -> int:
|
| 3 | if len(nums) == 1:
|
| 4 | return nums[0]
|
| 5 |
|
| 6 | def helper(sub_nums):
|
| 7 | memo = {}
|
| 8 | def dp(i):
|
| 9 | if i < 0:
|
| 10 | return 0
|
| 11 | if i in memo:
|
| 12 | return memo[i]
|
| 13 |
|
| 14 | result = max(sub_nums[i] + dp(i - 2), dp(i - 1))
|
| 15 | memo[i] = result
|
| 16 | return result
|
| 17 | return dp(len(sub_nums) - 1)
|
| 18 |
|
| 19 | return max(helper(nums[:-1]), helper(nums[1:])) |
Step-by-Step Solution
Handle Single House Edge Case
| 3 | if len(nums) == 1:
|
| 4 | return nums[0]
|
Objective
To immediately return the amount in the single house when the input list contains only one house.
Key Insight
When there is only one house, the circular adjacency constraint is irrelevant, and the maximum amount is simply the value of that house. Handling this edge case separately avoids unnecessary recursion and simplifies the main logic.
Interview Quick-Check
State & Boundaries
Check if the input list length is 1 and return the single value immediately to handle the trivial case.
Define Memoized DP Helper for Linear House Robbery
To compute the maximum robbery amount for a linear list of houses using top-down DP with memoization.
Compute Maximum Robbery by Comparing Two Linear Cases
To solve the circular problem by applying the helper to two linear subproblems and returning the maximum result.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
result = max(sub_nums[i] + dp(i - 2), dp(i - 1))Calculate max robbery by choosing to rob house i plus dp(i-2) or skip house i and take dp(i-1).
This recurrence captures the core DP decision: robbing the current house plus the best from two houses before, or skipping it to take the best from the previous house, ensuring no two adjacent houses are robbed.
if i in memo:Return cached result if index i has been computed before.
Memoization lookup avoids recomputation, ensuring each subproblem is solved once.
return max(helper(nums[:-1]), helper(nums[1:]))Return the maximum robbery amount between robbing houses excluding the last or excluding the first.
This line implements the key insight that the circular problem can be solved by comparing two linear subproblems, each excluding one of the conflicting houses, ensuring the circular adjacency constraint is respected.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why does solving two linear subproblems—excluding the first house in one and the last house in the other—correctly handle the circular adjacency constraint?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct House Robber II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the House Robber II drill