169. House Robber II

Houses are arranged in a circle, so the very first and the very last houses are now adjacent — robbing both would set off the alarm. Split the circle into two linear cases: "rob without the last house" and "rob without the first house". The answer is the max of the two; each is a standard linear House Robber.

Why splitting is correct

Whatever the optimal robbery is, it either includes house 0 or it doesn't.

• If it includes house 0, it can't include house n - 1 (they're adjacent on the circle). So we're robbing some subset of nums[0 .. n - 2].
• If it doesn't include house 0, we can freely consider nums[1 .. n - 1].

So answer = max(rob_line(nums[:-1]), rob_line(nums[1:])) covers both possibilities.

The linear House Robber sub-routine

For a non-circular row of houses, define dp[i] = max loot from nums[0..i]. At each house we either:

• Skip it: dp[i] = dp[i-1].
• Rob it: dp[i] = dp[i-2] + nums[i] (can't take the previous house's value).

Take the max. We only ever need dp[i-1] and dp[i-2], so two rolling variables suffice.

Steps

1. Edge case: if the list has one house, return that value (no "adjacent" issue when there's only one).
2. Define rob_line(arr): walk arr left-to-right with prev = curr = 0, updating prev, curr = curr, max(curr, prev + x) at each step. Return curr.
3. Return max(rob_line(nums[:-1]), rob_line(nums[1:])).

Walk-through

nums = [2, 3, 2] (circular).

• rob_line([2, 3]):
  • x = 2: prev, curr = 0, max(0, 0+2) = 2.
  • x = 3: prev, curr = 2, max(2, 0+3) = 3.
  • returns 3.
• rob_line([3, 2]):
  • x = 3: prev, curr = 0, 3.
  • x = 2: prev, curr = 3, max(3, 0+2) = 3.
  • returns 3.
• max(3, 3) = 3. ✓

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

• rob_line([1, 2, 3]): walks to (3, 4) → returns 4.
• rob_line([2, 3, 1]): walks to (3, 4) → returns 4.
• Answer: 4.

Edge cases

• Single house: can rob it alone.
• Two houses: robbing both would be circular-adjacent, so the answer is max(nums[0], nums[1]). Both rob_line slices are length-1 and return that single value's max.

Complexity

• Time: O(n) — two linear sweeps.
• Space: O(1) — two scalars per sweep.

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robLine(nums, 0, nums.length - 2), robLine(nums, 1, nums.length - 1));
    }

    private int robLine(int[] nums, int lo, int hi) {
        int prev = 0, curr = 0;
        for (int i = lo; i <= hi; i++) {
            int temp = curr;
            curr = Math.max(curr, prev + nums[i]);
            prev = temp;
        }
        return curr;
    }
}