House Robber II — Circular Arrangement

Problem Statement

You are a robber planning to rob houses arranged in a circle. Each house has some money. Adjacent houses have connected security systems — if two adjacent houses are robbed on the same night, the alarm triggers.

Because the houses are in a circle, the first and last houses are also adjacent.

Return the maximum amount you can rob without triggering the alarm.

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

Example

Input: nums = [2, 3, 2]

Output: 3

Explanation: You can't rob house 0 (money=2) and house 2 (money=2) because they're adjacent (circular). So rob house 1 → 3.

Input: nums = [1, 2, 3, 1]

Output: 4

Explanation: Rob house 0 (money=1) and house 2 (money=3) → 4.

What the Interviewer Expects

1. Recognize the circular twist — the linear House Robber DP doesn't directly work because first and last are adjacent.
2. Key insight — split into two cases:
   • Case A: rob houses 0 to n-2 (exclude last)
   • Case B: rob houses 1 to n-1 (exclude first)
   • Answer = max of the two cases
   • This breaks the circular dependency into two linear subproblems
3. Linear House Robber DP for each case: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
4. Edge case — single house: return nums[0].
5. Space optimization — O(1) using two rolling variables instead of a DP array.

Follow-ups

1. What if the houses were in a straight line (original House Robber)? How does it simplify?
2. What if you could rob at most K houses total?
3. What if houses were arranged in a binary tree (House Robber III)?
4. Can you do it with O(1) space?