House Robber II

1. Problem & Core Objective

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

nums = [2,3,2]      →  3      can't take both 2s; take the 3
nums = [1,2,3,1]    →  4      rob houses 0 and 2
nums = [1,2,3]      →  3

Constraints: 1 <= nums.length <= 100 · 0 <= nums[i] <= 1000

What's actually being tested: reducing a circular constraint to two linear ones. The insight is that house 0 and house n−1 can't both be robbed, so split on that one decision and reuse the previous question's solution unchanged.

2. First-Principles Thought Process

What the circle actually adds

Exactly one new constraint: houses 0 and n−1 are adjacent.

Everything else is identical to House Robber. So the question is how to enforce that single extra rule without rewriting the recurrence.

Case-split on the first house

Any valid selection either includes house 0 or it doesn't, and those cases are exhaustive and disjoint:

• House 0 is robbed → house n−1 cannot be → solve linearly on nums[0 .. n−2]
• House 0 is not robbed → house n−1 is free → solve linearly on nums[1 .. n−1]

Take the larger. Both subproblems are ordinary House Robber.

return Math.max(robLinear(nums, 0, n - 2),
                robLinear(nums, 1, n - 1));

Why this covers every case

The two ranges overlap on houses 1 .. n−2, which is fine — overlapping isn't double-counting, because we take a max over two independent computations, not a sum.

And every valid circular selection falls into at least one case: if it omits house 0, the second range covers it; if it omits house n−1, the first does. It can't include both, so at least one omission always exists.

Note the second case doesn't force house n−1 to be robbed — it merely permits it. That's why "not robbing house 0" and "solving on 1..n−1" are equivalent rather than one being stricter.

The n == 1 trap

With one house, nums[0 .. n−2] is nums[0 .. −1] — an empty range. The answer should be nums[0], so this needs an explicit guard or a range helper that handles emptiness.

3. Solution Paths

Approach 1 — Enumerate valid subsets with the circular check (brute force)

public int rob(int[] nums) {
    int n = nums.length;
    int best = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (!valid(mask, n)) continue;
        int sum = 0;
        for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0) sum += nums[i];
        best = Math.max(best, sum);
    }
    return best;
}

private boolean valid(int mask, int n) {
    for (int i = 0; i < n; i++)
        if ((mask & (1 << i)) != 0 && (mask & (1 << ((i + 1) % n))) != 0) return false;
    return true;                                    // % n makes it circular
}

• Time O(2^n · n) · Space O(1)

Counter-questions on this approach

⭐ "What does (i + 1) % n express?"

The circularity. Checking index n−1's neighbour wraps around to index 0, which is exactly the extra constraint.

It's the most direct encoding of the problem, and it's why this version is worth writing — it makes the only difference from House Robber explicit before optimising it away.

"Why is it O(2^n · n)?"

2^n subsets, each validated in O(n). At n = 100 that's 10^30 — hopeless. The constraint caps n at 100 precisely because the intended solution is linear.

"Could you at least prune invalid masks early?"

Yes, with backtracking that never places two adjacent bits. That cuts the count to the Lucas numbers, which still grow exponentially — about 1.6^n. Better, still infeasible.

Approach 2 — Two linear passes (optimal)

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];                     // no circle to break

    return Math.max(robRange(nums, 0, n - 2),       // house 0 allowed, last excluded
                    robRange(nums, 1, n - 1));      // house 0 excluded, last allowed
}

private int robRange(int[] nums, int lo, int hi) {
    int twoBack = 0, oneBack = 0;
    for (int i = lo; i <= hi; i++) {
        int current = Math.max(nums[i] + twoBack, oneBack);
        twoBack = oneBack;
        oneBack = current;
    }
    return oneBack;
}

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

Trace — nums = [2,3,2]:

• Time O(n) — two passes · Space O(1)

Counter-questions on this approach

⭐ "Why is splitting on house 0 sufficient? Don't you need to split on house n−1 too?"

No, because the two cases are already exhaustive. Any valid circular selection must omit at least one of house 0 and house n−1 — they're adjacent, so it can't contain both.

If it omits house 0, the range 1..n−1 can produce it. If it omits house n−1, the range 0..n−2 can. Every valid selection is therefore achievable in at least one of the two subproblems, and neither subproblem can produce an invalid one — because within a linear range, house 0 and house n−1 are never both present.

So the max over the two is exactly the circular optimum.

⭐ "The two ranges overlap on 1..n−2. Isn't that double-counting?"

No — they're two independent computations, and I take the maximum, not the sum. Overlap only means some selections are reachable in both cases, which is harmless.

Double-counting would matter if I were adding the results, which I'm not.

⭐ "Does the second range force house n−1 to be robbed?"

No, and this is worth being precise about. robRange(1, n−1) finds the best selection within that range — it may or may not include house n−1.

So the two cases aren't "rob 0" and "rob n−1"; they're "house n−1 is unavailable" and "house 0 is unavailable". That framing makes the exhaustiveness argument cleaner.

"Why is n == 1 special?"

Because robRange(0, n−2) becomes robRange(0, −1) — an empty range returning 0 — and robRange(1, 0) is also empty. The max would be 0 instead of nums[0].

The helper does handle empty ranges gracefully by returning 0, so it doesn't crash. It just returns the wrong answer, which is worse.

"What about n == 2?"

robRange(0, 0) gives nums[0] and robRange(1, 1) gives nums[1], so the max is the larger — correct, since two adjacent houses in a circle mean you take one.

No special case needed, which is worth checking rather than assuming.

"Why does robRange need lo and hi rather than reusing the whole-array version?"

Because the whole point is solving on a sub-range. Passing indices avoids copying sub-arrays, which would be O(n) per call and pointless.

Comparison

4. Why the Optimal Wins

The circular constraint looks like it needs a new recurrence. It doesn't — it needs a case split.

Because houses 0 and n−1 can't both be robbed, every valid selection omits at least one of them, and each omission reduces the problem to an ordinary linear House Robber on a sub-range. Two O(n) passes and a max.

That's the general technique: when a constraint links the two ends, split on it and solve the linear cases. It reappears in circular-array problems throughout.

The framing worth keeping:

A circular constraint becomes two linear problems. Houses 0 and n−1 can't both be robbed, so solve on 0..n−2 and on 1..n−1 and take the larger — neither range can contain both ends.

5. Java Prerequisites

Range-based helper — avoids copying sub-arrays:

private int robRange(int[] nums, int lo, int hi) { ... for (int i = lo; i <= hi; i++) ... }

Empty range returns 0 — robRange(0, -1) never enters the loop, which is why the n == 1 guard is needed rather than a crash.

Circular index — (i + 1) % n in the brute force; not needed once the case split removes the circularity.

Rolling variables seeded at 0 — reused verbatim from House Robber.

6. Interview Communication Guide

Clarifying questions: Are the first and last houses adjacent (yes — that's the whole difference)? Can n be 1 (yes — and it's the special case)? Non-negative values (yes)? Must I rob at least one (no, but non-negativity means robbing nothing is never better)?

The pitch

"The circle adds exactly one new constraint: houses 0 and n−1 are adjacent. Everything else is ordinary House Robber.

So rather than writing a new recurrence, I case-split on that one constraint. Any valid selection must omit at least one of the two end houses, since it can't contain both. That gives two cases:

• house n−1 unavailable → solve linearly on 0..n−2
• house 0 unavailable → solve linearly on 1..n−1

Take the larger. Both are ordinary House Robber, so I reuse that solution unchanged with a range parameter.

The argument that this is exhaustive: every valid circular selection omits at least one end, so it's producible in at least one range. And neither range can produce an invalid selection, because within a linear range the two ends are never both present.

The ranges overlap on 1..n−2, which is fine — I'm taking a max over two independent computations, not summing them.

One thing to be precise about: the second case doesn't force robbing house n−1, it just permits it. Framing the cases as 'which end is unavailable' rather than 'which end is robbed' makes the exhaustiveness cleaner.

Two O(n) passes, O(1) space.

The one special case is n == 1 — the range 0..n−2 is empty, so both passes return 0 and the answer would be 0 instead of nums[0]. n == 2 needs no guard: the two ranges give nums[0] and nums[1], and the max is right."

Edge cases to volunteer:

Name [5,1,1,5]. In a line the answer is 10 — both 5s. In a circle they're adjacent, so the best is 6 (5 + 1, houses 0 and 2). It's the clearest demonstration that the circularity actually bites, and a solution that forgets the case split returns 10.

7. Follow-Up Questions — Modified Constraints

⭐ "Return which houses were robbed."

Run both passes with decision tracking, see which produced the larger total, and reconstruct from that one. O(n) extra space, and it forfeits the O(1) rolling — the same trade as in the linear version.

⭐ "What if the houses formed a circular TREE — a ring with branches?"

Cut the ring at one edge and solve the resulting tree twice, once forcing each endpoint of the cut edge to be unrobbed. Same case-split idea, applied to a harder structure.

"What if you couldn't rob houses within distance k in the circle?"

The case split generalises but grows: you'd split on the first k houses' inclusion pattern, giving O(k) linear passes. Still polynomial, but the constant grows with k.

"What if the circle had 10^6 houses?"

Two O(n) passes with O(1) space scales directly. Values at 1000 each over 500,000 robbed houses caps at 5 × 10^8 — inside int, but close enough that I'd use long if the bound loosened.

"Solve it in a single pass instead of two."

You can track both cases simultaneously with four rolling variables — two per case. Same complexity, marginally fewer array traversals, noticeably harder to read. I'd take the two clear passes.

"What if robbing a house gave a bonus for also robbing the one two away?"

The reward is no longer decomposable into independent per-house values, so the take-or-skip recurrence breaks. You'd need a state carrying whether the previous-previous house was robbed — doubling the state space but still linear.