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
The 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. Taking the maximum of these two solves the original circular problem optimally.
Optimal Approach
Define 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. This approach respects the circular constraint and runs efficiently.
Time
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
| 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)
|
Objective
To compute the maximum robbery amount for a linear list of houses using top-down DP with memoization.
Key Insight
The classic House Robber problem can be solved by deciding at each house whether to rob it (and add its value to the result two houses before) or skip it (and take the result from the previous house). Memoization avoids redundant computations by caching results for each index. This helper function encapsulates this logic for any linear subarray of houses.
Interview Quick-Check
Core Logic
At each house index i, the maximum amount is the max between robbing house i plus dp(i-2), or skipping house i and taking dp(i-1). Memoization ensures each state is computed once.
State & Boundaries
Base case returns 0 when index i is less than 0, representing no houses left to rob.
Common Pitfalls & Bugs
Forgetting to memoize results leads to exponential recursion. Also, incorrect base cases can cause index errors or incorrect results.
Compute Maximum Robbery by Comparing Two Linear Cases
| 19 | return max(helper(nums[:-1]), helper(nums[1:])) |
Objective
To solve the circular problem by applying the helper to two linear subproblems and returning the maximum result.
Key Insight
Because the first and last houses are adjacent, robbing both is forbidden. By computing the maximum robbery amount excluding the last house and excluding the first house, the algorithm covers all valid scenarios. Taking the maximum of these two results yields the optimal solution for the circular arrangement.
Interview Quick-Check
Core Logic
The final answer is the maximum between robbing houses from index 0 to n-2 and from index 1 to n-1, ensuring the circular adjacency constraint is respected.
Common Pitfalls & Bugs
Failing to exclude either the first or last house in one of the subproblems can lead to invalid solutions that rob adjacent houses in the circle.
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.
memo = {}Initialize a memoization dictionary to cache results for subproblems.
Memoization prevents redundant recursive calls, reducing exponential recursion to linear time complexity.
if i < 0:Return 0 if index i is less than 0, representing no houses left.
This base case terminates recursion and correctly models that no money can be robbed from an empty set of houses.
memo[i] = resultStore the computed result in memo for index i.
Caching the result ensures that future calls for index i return instantly, preventing exponential recursion.
return dp(len(sub_nums) - 1)Return the maximum robbery amount for the entire sublist.
Starts the recursion from the last house in the sublist, triggering the full DP computation.
if len(nums) == 1:Check if the input list contains only one house.
This early check handles the trivial edge case where the circular constraint is irrelevant, allowing immediate return of the single house's value without further computation.
return nums[0]Return the amount in the single house.
Returning the single house's value is correct because no adjacency constraints apply when only one house exists.
def dp(i):Define the recursive dp function that computes max robbery up to index i.
This function models the problem as a state machine where each state represents the maximum robbery amount considering houses up to index i.
return memo[i]Retrieve memoized result for index i.
Accessing cached results is essential for efficient DP.
return resultReturn the computed maximum robbery amount for index i.
Returns the optimal solution for the subproblem up to house i, enabling recursive buildup of the final answer.
def helper(sub_nums):Define a helper function to solve the linear House Robber problem on a sublist.
Encapsulating the linear DP logic in a helper function allows reuse for both subproblems derived from the circular input.
return 0Return 0 for negative indices.
Ensures safe recursion termination and prevents index errors.
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?
Because the first and last houses are adjacent in the circle, they cannot both be robbed. By excluding the last house in one subproblem and the first house in the other, each subproblem represents a linear arrangement without circular adjacency, ensuring no invalid adjacent robberies. Taking the maximum of these two covers all valid possibilities.
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