You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3] Output: 3
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 1000Problem Overview: You are given an array where each element represents money stored in a house. Houses are arranged in a circle, so the first and last houses are neighbors. You cannot rob two adjacent houses. The task is to compute the maximum amount you can rob without triggering alarms.
The circular layout is the only difference from the classic House Robber problem. If you rob the first house, you cannot rob the last. If you rob the last house, you cannot rob the first. This constraint splits the problem into two independent linear subproblems.
Approach 1: Optimization with Memoization (Time: O(n), Space: O(n))
This approach uses dynamic programming with recursion and memoization. The key idea is the same as the original House Robber problem: for each index, decide whether to rob the current house or skip it. If you rob it, you add its value and move to i + 2; if you skip it, move to i + 1. Because the houses form a circle, you evaluate two scenarios: robbing within range [0, n-2] and robbing within range [1, n-1]. Each recursive state is cached to avoid recomputation, giving linear time complexity. This version is useful when you want a top‑down perspective that clearly expresses the decision tree.
Approach 2: Dynamic Programming with Two Passes (Time: O(n), Space: O(1))
This is the optimal iterative solution. Instead of recursion, compute the best robbery plan using two passes over the array. First pass assumes you rob houses from 0 to n-2 (excluding the last). Second pass assumes you rob houses from 1 to n-1 (excluding the first). Each pass runs the classic House Robber DP where you track two values: prev1 (max profit up to previous house) and prev2 (max profit up to the house before that). For every element, compute max(prev1, prev2 + nums[i]). Because only two variables are needed, space remains constant.
The insight is that the circular dependency disappears once you split the problem into these two linear ranges. Each pass solves a standard non‑adjacent selection problem using DP transitions.
Recommended for interviews: The dynamic programming two‑pass approach is what most interviewers expect. It runs in O(n) time with O(1) extra space and clearly demonstrates understanding of circular constraints. The memoization version still shows strong dynamic programming fundamentals and is often easier to reason about initially, but the iterative optimization shows stronger mastery.
This approach involves splitting the problem into two scenarios: robbing from house 0 to house n-2, and from house 1 to house n-1. The aim is to apply the linear version of the House Robber problem to each scenario separately and then take the maximum of the two resulting summed values.
This C solution defines a helper function robLinear for the simpler linear version of the House Robber problem, then uses this to calculate the maximum rob amount in two scenarios: excluding the first and last house respectively. The final result is the maximum of these two computed values.
Time Complexity: O(n).
Space Complexity: O(1).
This approach implements a memoized version of the dynamic programming solution to avoid recomputing values. We explore two scenarios of the circle, taking into account the cycles explicitly by caching intermediate results.
The C solution sets up a memo array for memoization to store calculated maximums for each house start index. It runs the helper function robHelper which recursively looks for the maximum stealing options, caching results for efficiency. It applies this to the scenarios that exclude the first and last house respectively.
Time Complexity: O(n).
Space Complexity: O(n) for the memoization array.
The circular arrangement means that at most one of the first and last houses can be chosen for theft, so this circular arrangement problem can be reduced to two single-row house problems.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Dynamic Programming with Two Passes | Time Complexity: O(n). |
| Optimization with Memoization | Time Complexity: O(n). |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Memoization (Top-Down DP) | O(n) | O(n) | When recursion is easier to reason about and you want explicit subproblem caching. |
| Dynamic Programming with Two Passes | O(n) | O(1) | Best practical solution. Handles circular constraint by solving two linear DP cases. |
DP 6. House Robber 2 | 1D DP | DP on Subsequences • take U forward • 484,417 views views
Watch 9 more video solutions →Practice House Robber II with our built-in code editor and test cases.
Practice on FleetCode