213. House Robber II

House Robber II is the sequel that looks harder than it is: bend the street into a circle, and the whole problem reduces to running plain House Robber twice. It’s a good lesson in turning a new constraint into a case split rather than a new algorithm.

The problem

Same rules as House Robber — no two adjacent houses — but now the houses are arranged in a circle, so the first and last are neighbors too. Return the most you can rob. (Full statement on LeetCode.)

Intuition: break the circle into two lines

The circle adds exactly one new conflict: you can’t rob both the first house and the last. Everything else is identical to the linear problem. So split on that single decision:

• If you don’t rob the first house, the rest is a straight line from house 1 to house n-1.
• If you don’t rob the last house, it’s a straight line from house 0 to house n-2.

Every valid plan falls into at least one of those two lines (whichever endpoint you gave up), so the answer is just the better of the two linear results:

$\text{answer} = \max\big(\text{rob}(\text{nums}[1{:}]),\; \text{rob}(\text{nums}[{:}n-1])\big)$

You never have to reason about the circle directly — you delete one house to cut it open, twice.

Solution

Reuse the linear solver on two ranges. The one edge case is a single house, which has no “circle” to speak of:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLine(nums, 0, n - 2),   // drop the last house
                        robLine(nums, 1, n - 1));   // drop the first house
    }

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

Complexity

	Time	Space
Two linear passes	$O(n)$	$O(1)$

Two sweeps over (almost) the whole array is still linear, and each sweep carries only two variables.

In an interview

The move that impresses is naming the reduction out loud: “the circle only forbids first-and-last together, so I run the linear robber on the array without the first house and again without the last, and take the max.” That reframes a scary-looking constraint as one case split over a function you’ve already written — exactly the kind of reuse 1D DP rewards. Don’t forget the single-house guard; it’s the off-by-one most people trip on here.

References

• LeetCode 213 — House Robber II