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.
Here’s the [Problem Link] to begin with.
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 <= 100
0 <= nums[i] <= 1000
How Does the “Circular” Constraint Change Things?
In the original House Robber, you could simply decide “rob or skip” for each house, moving linearly. Now, if you rob the first house, you can’t rob the last, and vice versa.
So, split into two scenarios:
- Rob houses 0 to n-2 (skip the last house).
- Rob houses 1 to n-1 (skip the first house).
Take the maximum of the two.
Let’s apply different DP approaches for each scenario.
Solution 1: Brute Force (Recursion)
Intuition
At every step, you have two choices:
- Pick the current house (and thus skip the previous one)
- Skip the current house (and take the best from earlier)
Because of the circular nature, we run the logic twice:
- Once excluding the last house (
nums[0 : n-1]
) - Once excluding the first house (
nums[1 : n]
)
Take the max of both results.
Detailed Approach
- Base Cases:
- If index == 0: Only one house, so rob it.
- If index == -1: No houses left, so rob nothing.
- Recursive Cases:
pick = nums[index] + solve(index-2, nums)
notpick = solve(index-1, nums)
- Return
max(pick, notpick)
- Do this for both possible slices.
Code
class Solution:
def solve(self, index, nums):
# If only one house left, rob it
if index == 0:
return nums[index]
# If no houses left, rob nothing
if index == -1:
return 0
# Option 1: Pick current house and move two steps back
pick = nums[index] + self.solve(index - 2, nums)
# Option 2: Skip current house and move one step back
notpick = self.solve(index - 1, nums)
# Return max loot possible at this index
return max(pick, notpick)
def rob(self, nums: List[int]) -> int:
# Base case: only one house (no circle constraint)
if len(nums) == 1:
return nums[0]
n = len(nums)
# Scenario 1: Rob from 0 to n-2
ans1 = self.solve(n - 2, nums[0 : n - 1])
# Scenario 2: Rob from 1 to n-1
ans2 = self.solve(n - 2, nums[1 : n])
# Return the best out of both possibilities
return max(ans1, ans2)
Code Explanation
solve(index, nums)
recursively computes the best you can do for a slice.- Careful splitting ensures the circle is not broken (never include both first and last house).
- Calls
solve
for both scenarios, returns the maximum possible loot.
Time and Space Complexity
- Time: O(2^n) – Each call can branch into two subproblems; exponential.
- Space: O(n) – Due to recursion stack.
Simplifying It
Think: You’re trying every possible rob/skip path for both possible ranges, but you forget the results of previous calculations. Practical only for small n.
Solution 2: Memoization (Top-Down DP)
Intuition
In brute force, the same subproblems are recalculated many times. Memoization adds a DP array to remember results for each index and subarray. Same two scenarios apply (exclude first, exclude last); now we save time by caching.
Detailed Approach
- DP array of length n-1 (as we slice nums to length n-1 each time).
- For each call, if value already computed (
dp[index] != -1
), return cached result. - Otherwise, compute as with recursion and store result in dp array.
Code
class Solution:
def solve(self, index, nums, dp):
# If only one house left, rob it
if index == 0:
return nums[index]
# If no houses left
if index == -1:
return 0
# Use cached value if available
if dp[index] != -1:
return dp[index]
# Option 1: Pick and add result from index-2
pick = nums[index] + self.solve(index - 2, nums, dp)
# Option 2: Skip current house
notpick = self.solve(index - 1, nums, dp)
dp[index] = max(pick, notpick)
return dp[index]
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
n = len(nums)
# Rob from 0 to n-2
dp1 = [-1] * (n - 1)
ans1 = self.solve(n - 2, nums[0 : n - 1], dp1)
# Rob from 1 to n-1
dp2 = [-1] * (n - 1)
ans2 = self.solve(n - 2, nums[1 : n], dp2)
return max(ans1, ans2)
Code Explanation
- Like pure recursion, but now each subproblem is solved just once, thanks to the dp array.
- Both slices (
nums[0:n-1]
andnums[1:n]
) use separate dp arrays, ensuring circle constraint is always satisfied.
Time and Space Complexity
- Time: O(n) per subarray (n-1), so O(n) total.
- Space: O(n) for DP arrays + O(n) for stack frames.
Simplifying It
Now you keep a notebook for each scenario and never recalculate any decision. Much faster, good for large n!
Solution 3: Tabulation (Bottom-Up DP)
Intuition
Instead of starting from end and recursing, fill up DP array from base to target using a for-loop. For each index, loot = max(current house + dp[index-2], dp[index-1]).
Detailed Approach
- For each scenario (exclude last or exclude first), make separate pass.
- Start with
dp = nums
- For each index,
- If index > 1:
pick = nums[index] + dp[index-2]
- Else:
pick = nums[index]
- not_pick = dp[index-1]
- dp[index] = max(pick, not_pick)
- If index > 1:
Code
class Solution:
def solve(self, nums):
n = len(nums)
dp = [-1] * n
dp[0] = nums[0]
for index in range(1, n):
# Pick current + two steps back if possible
if index > 1:
pick = nums[index] + dp[index - 2]
else:
pick = nums[index]
# Skip current, take previous result
not_pick = dp[index - 1]
dp[index] = max(pick, not_pick)
return dp[n - 1]
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
# Exclude last and exclude first scenarios
ans1 = self.solve(nums[0 : n - 1])
ans2 = self.solve(nums[1 : n])
return max(ans1, ans2)
Code Explanation
- The
solve
function fills dp array from left to right, building up possibilities step by step. - Main rob function checks for the single house case; otherwise, runs both possible cases.
Time and Space Complexity
- Time: O(n) per scenario, so O(n) total.
- Space: O(n) for dp array.
Simplifying It
You write a plan for each possible chain of houses, filling the results for each step, and never look back!
Solution 4: Space-Optimized Tabulation (Best Practice)
Intuition
While building the dp array, we only ever need the last two values. Replace array with two variables (prev
, prev2
) for memory efficiency; great for interviews!
Detailed Approach
- For each slice, initialize:
prev
as the value at index 0 (nums)prev2
to 0
- For each house, update:
- If index > 1:
- pick = nums[index] + prev2
- Else:
- pick = nums[index]
- not_pick = prev
- curr = max(pick, not_pick)
- Slide window: prev2 = prev; prev = curr
- If index > 1:
Code
class Solution:
def solve(self, nums):
n = len(nums)
prev = nums[0] # DP for index - 1
prev2 = 0 # DP for index - 2
for index in range(1, n):
# Pick current house and add loot from two steps back
if index > 1:
pick = nums[index] + prev2
else:
pick = nums[index]
# Skip current house, use prev result
not_pick = prev
curr = max(pick, not_pick)
# Update window
prev2 = prev
prev = curr
return prev
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
# Try both scenarios (excluding first or last house)
ans1 = self.solve(nums[0 : n - 1])
ans2 = self.solve(nums[1 : n])
return max(ans1, ans2)
Code Explanation
- Only two variables needed throughout; for each scenario, make a linear scan.
- Final answer is the better loot from both scenarios, so the circle is always respected.
Time and Space Complexity
- Time: O(n)
- Space: O(1) (just variables, not arrays)
Simplifying It
It’s like moving through the houses with a calculator, only tracking the last two amounts, always keeping memory and speed at max efficiency!
Summary Table
Approach | Time | Space | Difficulty | Use Case |
---|---|---|---|---|
Recursion (Brute Force) | O(2^n) | O(n) | Easy | Understanding choices |
Memoization (Top-Down DP) | O(n) | O(n) | Medium | Learning DP, larger n |
Tabulation (Bottom-Up DP) | O(n) | O(n) | Medium | Iteration-based DP |
Space-Optimized Tabulation | O(n) | O(1) | Medium-Hard | Best for interviews/coding |
Conclusion
The House Robber II problem is a powerful demonstration of how a small twist (the circular street) can change a familiar dynamic programming pattern. Start with recursion for clarity, move through memoization and tabulation, and finish with sleek space optimization for interviews or production code. Practice with variants like “House Robber I” and related DP problems to reinforce your foundations.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.