You're planning a heist on a cul-de-sac where the houses sit around a loop — the last house's backyard touches the first house's. Each house holds some loot, and any two houses next to each other share an alarm, so robbing both gets you caught. Because the street wraps, the first and last houses count as neighbours too. Given the loot in each house, return the largest total you can take without ever robbing two adjacent houses. This is the classic House Robber II problem.
// houses: array of non-negative numbers, arranged in a CIRCLE
// (houses[0] and houses[n-1] are adjacent).
// returns: the maximum total loot with no two adjacent houses robbed.
function neighborhoodTheftCircular(houses: number[]): number;neighborhoodTheftCircular([2, 3, 2]); // → 3
// Houses 0 and 2 both hold 2, but they're adjacent on the loop,
// so you can't take both. The lone middle house (3) wins.neighborhoodTheftCircular([1, 2, 3, 1]); // → 4
// Rob house 0 (1) and house 2 (3) → 4. They aren't adjacent,
// and neither is a wrap-around neighbour of the other.houses[0] and houses[n - 1] are neighbours. You can rob at most one of them.[] returns 0 (nothing to steal).[v] returns v. A lone house has no neighbours at all, so it's always safe to rob.[a, b] returns max(a, b). On a ring of two, the houses are neighbours both ways, so you take only the richer one.≥ 0; you never lose money by robbing a house.You'll turn one hard circular problem into two easy straight-line ones, solve each with the standard house-robber scan, and keep the better answer.
Same heist as the straight-street version — rob houses for the most loot, but never two that touch — with one twist: the street is a loop. The last house's wall backs onto the first house's, so houses 0 and n - 1 are neighbours too. That single extra edge is the whole difficulty. On a straight street you only worry about the house immediately behind you; on a ring you also have to make sure you didn't quietly rob both ends, because the ends are now next to each other.
The wrap-around edge connects exactly two houses: the first and the last. Everything else about the ring is identical to a straight line. So the only new rule is "you can't rob both house 0 and house n - 1." There are only two ways to obey it: don't rob the first house, or don't rob the last house. If you commit to leaving one of them out, the ring effectively snaps open into a plain straight street — and you already know how to solve that.
So solve the ring as the better of two straight streets: one that drops the last house, one that drops the first. Neither street contains both wrap-around neighbours, so neither can accidentally rob both ends — and together they cover every legal robbery of the ring.
The obvious move is to reuse the linear house-robber scan directly. We have a working robLinear that walks a row keeping two rolling totals (prev2, prev1) and at each house takes max(skip, rob). Just feed it the whole circle:
function robLinear(houses) {
let prev2 = 0;
let prev1 = 0;
for (const loot of houses) {
const cur = Math.max(prev1, loot + prev2);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
function neighborhoodTheftCircular(houses) {
return robLinear(houses); // treat the ring as if it were a straight line
}This is right for a straight street and wrong for a ring, because robLinear has no idea the two ends touch. It happily robs house 0 and house n - 1 whenever both are profitable — exactly the move the loop forbids. On [100, 1, 1, 100] it grabs both 100s and returns 200; on the real ring those two houses are neighbours, so the best you can legally do is 101.
Fix the blind spot by never letting a single scan see both ends. Run robLinear twice: once on houses[0 .. n-2] (drop the last house) and once on houses[1 .. n-1] (drop the first house). Each run is missing one of the two wrap-around neighbours, so neither can rob both — and the larger of the two results is the answer. The tiny rings (n of 0, 1, 2) can't be split into a meaningful "drop one end" pair, so handle them up front.
function robLinear(houses) {
// Standard linear house-robber: two rolling totals, max(skip, rob) per house.
let prev2 = 0;
let prev1 = 0;
for (const loot of houses) {
const cur = Math.max(prev1, loot + prev2);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
function neighborhoodTheftCircular(houses) {
const n = houses.length;
// No houses → nothing to steal.
if (n === 0) return 0;
// One house has no neighbours (it isn't adjacent to itself), so rob it.
// Crucial: we CANNOT use the "drop an end" trick here — dropping the only
// house leaves an empty street, which would wrongly return 0.
if (n === 1) return houses[0];
// Two houses on a ring are neighbours both ways; take only the richer.
if (n === 2) return Math.max(houses[0], houses[1]);
// Drop the last house, then drop the first house. Each straight run is
// missing one wrap-around neighbour, so neither can rob both ends.
const withoutLast = robLinear(houses.slice(0, n - 1)); // houses[0 .. n-2]
const withoutFirst = robLinear(houses.slice(1)); // houses[1 .. n-1]
return Math.max(withoutLast, withoutFirst);
}
module.exports = { neighborhoodTheftCircular };The key shift from the naive version is that we never solve "the ring" directly. We reduce it to a problem we've already solved — the straight street — by physically removing one end before each scan. withoutLast covers every legal robbery that skips the last house; withoutFirst covers every one that skips the first. Any valid ring robbery skips at least one of the two ends (it can't take both), so it lands in at least one of the two runs, and Math.max keeps the winner. The n === 1 guard earns its place: there's no "drop one end and keep the other" option when there's only one house, so the split would silently return 0 instead of the house's value.
Inside each run, robLinear is the ordinary one-dimensional DP: at each house the best total is max(prev1, loot + prev2) — skip this house and inherit the previous best, or rob it and add the best from two houses back. Two scalars slide along the row, so each scan is O(n) time and O(1) space. Two scans plus the slice copies stay O(n) overall.
Trace neighborhoodTheftCircular([200, 3, 140, 20, 10]). Here n = 5, so we skip the small-ring guards and run the two straight scans.
Run 1 — exclude the last house. The row is houses[0 .. 3] = [200, 3, 140, 20]. Start prev2 = 0, prev1 = 0.
cur = max(0, 200 + 0) = 200. Slide: prev2 = 0, prev1 = 200.cur = max(200, 3 + 0) = 200. Slide: prev2 = 200, prev1 = 200. Robbing the 3 alone can't beat the 200 already banked.cur = max(200, 140 + 200) = 340. Slide: prev2 = 200, prev1 = 340. Now 140 + 200 (house 2 plus the best from two back, house 0's 200) wins — we've chosen {0, 2}.cur = max(340, 20 + 200) = 340. Slide: prev2 = 340, prev1 = 340. Adding house 3 forces dropping house 2; 20 + 200 = 220 loses, so skip it.Run 1 returns 340.
Run 2 — exclude the first house. The row is houses[1 .. 4] = [3, 140, 20, 10]. Reset prev2 = 0, prev1 = 0.
cur = max(0, 3) = 3. → prev2 = 0, prev1 = 3.cur = max(3, 140 + 0) = 140. → prev2 = 3, prev1 = 140.cur = max(140, 20 + 3) = 140. → prev2 = 140, prev1 = 140.cur = max(140, 10 + 140) = 150. → prev2 = 140, prev1 = 150.Run 2 returns 150.
The answer is Math.max(340, 150) = 340 — rob houses 0 and 2 (200 + 140). Notice run 1 found this because it was allowed to take house 0; run 2, which dropped house 0, never could. That's exactly why we run both and keep the larger.
robLinear([100, 1, 1, 100]) returns 200 by taking houses 0 and 3 — but on a ring those are neighbours. Fix: never give a single scan both ends; split into "exclude first" and "exclude last."1 .. n-2 behave exactly as on a straight street. Don't add extra wrap-around checks between interior houses — there aren't any. Just the two ends.n === 1 must be special-cased. A lone house has no neighbours, so the answer is its value. But the split would compute robLinear([]) on both runs (dropping the only house leaves nothing) and return 0. Guard n === 1 before splitting.n === 2 must be special-cased too. With two houses, "exclude last" is [houses[0]] and "exclude first" is [houses[1]]; their max is max(houses[0], houses[1]), which is actually correct here — but it's clearer and safer to return Math.max(houses[0], houses[1]) directly so the intent (they're mutual neighbours) is explicit.slice(0, n - 1) excludes the LAST, slice(1) excludes the FIRST. It's easy to flip these. slice(0, n - 1) keeps indices 0 .. n-2; slice(1) keeps 1 .. n-1. Swapping them gives the same Math.max here, but the mental labels matter when you reconstruct which houses were robbed.prev2/prev1 loop a second time inside the circular function, stop: call robLinear twice instead. One bug-free scan beats two copies that can drift apart.robLinear keep its full best[] array and walk it backward (best[i] === best[i-1] means house i was skipped). Run it on both sliced rows, then map the winning run's indices back to the original ring positions — remembering the +1 offset on the "exclude first" run.robLinear helper alone. House Robber III puts the houses on a binary tree: a post-order DFS returns two values per node (best if you rob it, best if you don't), and the parent combines its children the same "rob vs. skip" way.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're planning a heist on a cul-de-sac where the houses sit around a loop — the last house's backyard touches the first house's. Each house holds some loot, and any two houses next to each other share an alarm, so robbing both gets you caught. Because the street wraps, the first and last houses count as neighbours too. Given the loot in each house, return the largest total you can take without ever robbing two adjacent houses. This is the classic House Robber II problem.
// houses: array of non-negative numbers, arranged in a CIRCLE
// (houses[0] and houses[n-1] are adjacent).
// returns: the maximum total loot with no two adjacent houses robbed.
function neighborhoodTheftCircular(houses: number[]): number;neighborhoodTheftCircular([2, 3, 2]); // → 3
// Houses 0 and 2 both hold 2, but they're adjacent on the loop,
// so you can't take both. The lone middle house (3) wins.neighborhoodTheftCircular([1, 2, 3, 1]); // → 4
// Rob house 0 (1) and house 2 (3) → 4. They aren't adjacent,
// and neither is a wrap-around neighbour of the other.houses[0] and houses[n - 1] are neighbours. You can rob at most one of them.[] returns 0 (nothing to steal).[v] returns v. A lone house has no neighbours at all, so it's always safe to rob.[a, b] returns max(a, b). On a ring of two, the houses are neighbours both ways, so you take only the richer one.≥ 0; you never lose money by robbing a house.You'll turn one hard circular problem into two easy straight-line ones, solve each with the standard house-robber scan, and keep the better answer.
Same heist as the straight-street version — rob houses for the most loot, but never two that touch — with one twist: the street is a loop. The last house's wall backs onto the first house's, so houses 0 and n - 1 are neighbours too. That single extra edge is the whole difficulty. On a straight street you only worry about the house immediately behind you; on a ring you also have to make sure you didn't quietly rob both ends, because the ends are now next to each other.
The wrap-around edge connects exactly two houses: the first and the last. Everything else about the ring is identical to a straight line. So the only new rule is "you can't rob both house 0 and house n - 1." There are only two ways to obey it: don't rob the first house, or don't rob the last house. If you commit to leaving one of them out, the ring effectively snaps open into a plain straight street — and you already know how to solve that.
So solve the ring as the better of two straight streets: one that drops the last house, one that drops the first. Neither street contains both wrap-around neighbours, so neither can accidentally rob both ends — and together they cover every legal robbery of the ring.
The obvious move is to reuse the linear house-robber scan directly. We have a working robLinear that walks a row keeping two rolling totals (prev2, prev1) and at each house takes max(skip, rob). Just feed it the whole circle:
function robLinear(houses) {
let prev2 = 0;
let prev1 = 0;
for (const loot of houses) {
const cur = Math.max(prev1, loot + prev2);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
function neighborhoodTheftCircular(houses) {
return robLinear(houses); // treat the ring as if it were a straight line
}This is right for a straight street and wrong for a ring, because robLinear has no idea the two ends touch. It happily robs house 0 and house n - 1 whenever both are profitable — exactly the move the loop forbids. On [100, 1, 1, 100] it grabs both 100s and returns 200; on the real ring those two houses are neighbours, so the best you can legally do is 101.
Fix the blind spot by never letting a single scan see both ends. Run robLinear twice: once on houses[0 .. n-2] (drop the last house) and once on houses[1 .. n-1] (drop the first house). Each run is missing one of the two wrap-around neighbours, so neither can rob both — and the larger of the two results is the answer. The tiny rings (n of 0, 1, 2) can't be split into a meaningful "drop one end" pair, so handle them up front.
function robLinear(houses) {
// Standard linear house-robber: two rolling totals, max(skip, rob) per house.
let prev2 = 0;
let prev1 = 0;
for (const loot of houses) {
const cur = Math.max(prev1, loot + prev2);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
function neighborhoodTheftCircular(houses) {
const n = houses.length;
// No houses → nothing to steal.
if (n === 0) return 0;
// One house has no neighbours (it isn't adjacent to itself), so rob it.
// Crucial: we CANNOT use the "drop an end" trick here — dropping the only
// house leaves an empty street, which would wrongly return 0.
if (n === 1) return houses[0];
// Two houses on a ring are neighbours both ways; take only the richer.
if (n === 2) return Math.max(houses[0], houses[1]);
// Drop the last house, then drop the first house. Each straight run is
// missing one wrap-around neighbour, so neither can rob both ends.
const withoutLast = robLinear(houses.slice(0, n - 1)); // houses[0 .. n-2]
const withoutFirst = robLinear(houses.slice(1)); // houses[1 .. n-1]
return Math.max(withoutLast, withoutFirst);
}
module.exports = { neighborhoodTheftCircular };The key shift from the naive version is that we never solve "the ring" directly. We reduce it to a problem we've already solved — the straight street — by physically removing one end before each scan. withoutLast covers every legal robbery that skips the last house; withoutFirst covers every one that skips the first. Any valid ring robbery skips at least one of the two ends (it can't take both), so it lands in at least one of the two runs, and Math.max keeps the winner. The n === 1 guard earns its place: there's no "drop one end and keep the other" option when there's only one house, so the split would silently return 0 instead of the house's value.
Inside each run, robLinear is the ordinary one-dimensional DP: at each house the best total is max(prev1, loot + prev2) — skip this house and inherit the previous best, or rob it and add the best from two houses back. Two scalars slide along the row, so each scan is O(n) time and O(1) space. Two scans plus the slice copies stay O(n) overall.
Trace neighborhoodTheftCircular([200, 3, 140, 20, 10]). Here n = 5, so we skip the small-ring guards and run the two straight scans.
Run 1 — exclude the last house. The row is houses[0 .. 3] = [200, 3, 140, 20]. Start prev2 = 0, prev1 = 0.
cur = max(0, 200 + 0) = 200. Slide: prev2 = 0, prev1 = 200.cur = max(200, 3 + 0) = 200. Slide: prev2 = 200, prev1 = 200. Robbing the 3 alone can't beat the 200 already banked.cur = max(200, 140 + 200) = 340. Slide: prev2 = 200, prev1 = 340. Now 140 + 200 (house 2 plus the best from two back, house 0's 200) wins — we've chosen {0, 2}.cur = max(340, 20 + 200) = 340. Slide: prev2 = 340, prev1 = 340. Adding house 3 forces dropping house 2; 20 + 200 = 220 loses, so skip it.Run 1 returns 340.
Run 2 — exclude the first house. The row is houses[1 .. 4] = [3, 140, 20, 10]. Reset prev2 = 0, prev1 = 0.
cur = max(0, 3) = 3. → prev2 = 0, prev1 = 3.cur = max(3, 140 + 0) = 140. → prev2 = 3, prev1 = 140.cur = max(140, 20 + 3) = 140. → prev2 = 140, prev1 = 140.cur = max(140, 10 + 140) = 150. → prev2 = 140, prev1 = 150.Run 2 returns 150.
The answer is Math.max(340, 150) = 340 — rob houses 0 and 2 (200 + 140). Notice run 1 found this because it was allowed to take house 0; run 2, which dropped house 0, never could. That's exactly why we run both and keep the larger.
robLinear([100, 1, 1, 100]) returns 200 by taking houses 0 and 3 — but on a ring those are neighbours. Fix: never give a single scan both ends; split into "exclude first" and "exclude last."1 .. n-2 behave exactly as on a straight street. Don't add extra wrap-around checks between interior houses — there aren't any. Just the two ends.n === 1 must be special-cased. A lone house has no neighbours, so the answer is its value. But the split would compute robLinear([]) on both runs (dropping the only house leaves nothing) and return 0. Guard n === 1 before splitting.n === 2 must be special-cased too. With two houses, "exclude last" is [houses[0]] and "exclude first" is [houses[1]]; their max is max(houses[0], houses[1]), which is actually correct here — but it's clearer and safer to return Math.max(houses[0], houses[1]) directly so the intent (they're mutual neighbours) is explicit.slice(0, n - 1) excludes the LAST, slice(1) excludes the FIRST. It's easy to flip these. slice(0, n - 1) keeps indices 0 .. n-2; slice(1) keeps 1 .. n-1. Swapping them gives the same Math.max here, but the mental labels matter when you reconstruct which houses were robbed.prev2/prev1 loop a second time inside the circular function, stop: call robLinear twice instead. One bug-free scan beats two copies that can drift apart.robLinear keep its full best[] array and walk it backward (best[i] === best[i-1] means house i was skipped). Run it on both sliced rows, then map the winning run's indices back to the original ring positions — remembering the +1 offset on the "exclude first" run.robLinear helper alone. House Robber III puts the houses on a binary tree: a post-order DFS returns two values per node (best if you rob it, best if you don't), and the parent combines its children the same "rob vs. skip" way.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.