House Robber II

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbors.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

Return the maximum amount of money you can rob without alerting the police.

• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 200

Examples

How to think about it

This is House Robber II, where houses are in a circle. Because of the circular setup, the first and last house cannot both be robbed.

To handle the circular constraint, we split the problem into two linear cases:

• Rob from house 0 to n-2 (exclude last house)
• Rob from house 1 to n-1 (exclude first house)

Each subproblem becomes the classic House Robber I, which we can solve and then return the maximum of the two results.

1. Recursion — O(2ⁿ) time, O(n) space

The recursive function explores skipping the current house, or robbing it and jumping two steps. A flag is used to ensure that if the first house is robbed, the last house is not allowed.

2. Dynamic Programming (Top-Down) — O(n) time, O(n) space

We use a DP table memo[index][flag]. The index represents the current house, and the flag denotes whether the first house was robbed.

3. Dynamic Programming (Bottom-Up) — O(n) time, O(n) space

Because houses are in a circle, we split the problem into two linear cases. Each case uses a bottom-up DP array just like House Robber I.

4. Dynamic Programming (Space Optimized) — O(n) time, O(1) space

We run the Space Optimized House Robber I algorithm twice — once excluding the first house, and once excluding the last.

Where people go wrong

Forgetting the Single House Edge Case

When there is only one house, the circular constraint does not apply since there is no adjacency conflict. If you split the problem into nums[1:] and nums[:-1] without handling this case, both subarrays become empty when n=1, and the function returns 0 instead of nums[0]. Always check if the array has only one element and return its value directly.

Incorrectly Handling the Circular Constraint

The key insight is that the first and last houses cannot both be robbed. A common mistake is to add complex flag logic throughout the recursion when a simpler approach exists: run the standard House Robber algorithm twice, once excluding the first house and once excluding the last house.

Off-by-One Errors in Array Slicing

When splitting the array into nums[1:] (exclude first) and nums[:-1] (exclude last), be careful with slicing syntax. An off-by-one error here can lead to including both the first and last houses in one subproblem, or excluding more houses than intended.