House Robber II (LC 213) - Circular

Pattern: Dynamic Programming - Linear with Constraint
Difficulty: Medium
Key Concept: “Circular arrangement = solve two linear subproblems”

Problem Statement

Same as House Robber, but houses are in a circle. The first and last houses are adjacent.

---

The Strategy: Split and Conquer

Since we can’t rob both the first and last house:

1. Scenario A: Rob houses 0 to n-2 (ignore last)
2. Scenario B: Rob houses 1 to n-1 (ignore first)

$$Result = \max(Rob(0 \to n-2), ; Rob(1 \to n-1))$$

---

Java Implementation

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        return Math.max(
            robRange(nums, 0, nums.length - 2),
            robRange(nums, 1, nums.length - 1)
        );
    }

    private int robRange(int[] nums, int start, int end) {
        int prev2 = 0, prev1 = 0;

        for (int i = start; i <= end; i++) {
            int current = Math.max(prev1, nums[i] + prev2);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

---

Dry Run (houses = [2, 3, 2])

Scenario A: houses[0..1] = [2, 3]
  House 0: max(0, 2+0) = 2
  House 1: max(2, 3+0) = 3
  Result A = 3

Scenario B: houses[1..2] = [3, 2]
  House 1: max(0, 3+0) = 3
  House 2: max(3, 2+0) = 3
  Result B = 3

Answer: max(3, 3) = 3

---

Complexity

Approach	Time	Space
Space-Optimized	O(n)	O(1)