Pass A (skip last)
pass
The houses now form a circle, so the first and last are adjacent and cannot both be robbed. Break the cycle by running the classic linear House-Robber DP twice — once skipping the first house, once skipping the last — and returning the max of the two results.
Given nums where each element is the money in one house, rob the maximum total without robbing two adjacent houses. The twist: the houses are arranged in a circle, so house 0 and house n-1 are also adjacent. nums = [2,3,2] → 3 (rob only house 1; you cannot rob both house 0 and house 2 because they share the circular edge).
0 and house n-1 are never both robbed. So the optimal answer is either the best robbery on nums[0..n-2] (last house excluded) or the best on nums[1..n-1] (first house excluded). Each sub-problem is a plain linear House Robber — a problem you already know.n === 1, return nums[0]— there's only one house to rob.robRange(start, end) runs the rolling-pair DP on the slice [start..end]: maintain rob1 (best two houses back) and rob2 (best up to previous house). At each step, newRob2 = max(rob2, rob1 + nums[i]).robRange(0, n-2) — the last house is excluded so the first and last are no longer adjacent.robRange(1, n-1) — the first house is excluded instead.max(passA, passB). The optimum must lie in one of these two non-circular sub-problems.The rob1 / rob2 rolling pair needs only two variables per pass — no array required. The total extra space is O(1).
2 (dimmed). Initialize rob1=0, rob2=0.function rob(nums: number[]): number {
const n = nums.length;
if (n === 1) return nums[0];
function robRange(start: number, end: number): number {
let rob1 = 0;
let rob2 = 0;
for (let i = start; i <= end; i++) {
const newRob2 = Math.max(rob2, rob1 + nums[i]);
rob1 = rob2;
rob2 = newRob2;
}
return rob2;
}
// Houses form a circle: first and last are adjacent.
// Run linear DP twice: once excluding the last house,
// once excluding the first, then take the max.
return Math.max(robRange(0, n - 2), robRange(1, n - 1));
}nums[0]. Handling it early keeps the rest of the logic clean.robRange(start, end) is exactly the linear House Robber: rob1 holds the best value achievable two or more positions back; rob2 holds the best up to the previous position. newRob2 = max(rob2, rob1 + nums[i]) asks: "rob this house (worth rob1 + nums[i]) or skip it (keep rob2)?" Then slide the window forward.0 and house n-1 are never both optimal, the true answer is the max of robRange(0, n-2) (exclude last) and robRange(1, n-1) (exclude first). The circular constraint is fully handled by the range bounds — no special casing inside the DP.n-1. O(1) extra space — only rob1 and rob2 per pass, no auxiliary array.parent[] array during each pass to reconstruct the chosen indices, then return the set from whichever pass won.2ⁿ subsets, filter out those with adjacent or wrap-around pairs, and take the max sum. The DP replaces this with two O(n) passes.robRange(0, n-1). The circular version is strictly harder because it adds one extra adjacency constraint.k — maintain a sliding-window max with a deque instead of two variables.[withRoot, withoutRoot]pair from each subtree. The pattern is the same "take vs skip" DP, just on a tree shape.| houses in a circle, no two adjacent | two-pass linear House Robber DP |
| circular array, first↔last adjacency | decompose into two [0..n-2] / [1..n-1] sub-problems |
| rolling rob1/rob2 in a loop | linear DP, O(1) space |
| "what if it wraps around?" | exclude one endpoint per pass, take max |
function rob(nums: number[]): number {
const n = nums.length;
if (n === 1) return nums[0];
function robRange(start: number, end: number): number {
let rob1 = 0, rob2 = 0;
for (let i = start; i <= end; i++) {
const next = Math.max(rob2, rob1 + nums[i]);
rob1 = rob2;
rob2 = next;
}
return rob2;
}
return Math.max(robRange(0, n - 2), robRange(1, n - 1));
}0 and house n-1are adjacent in the circle, creating a dependency between the first and last decisions that a left-to-right pass can't express cleanly.nums = [2,3,2]. What does Pass A (robRange(0, 1)) return?robRange(0, n-1) for both passes (ignoring the circular constraint). What goes wrong?