Houses are arranged in a circle, each holding some amount of money. You can't take from two adjacent houses, and because the houses form a circle, the first and last are also adjacent. Return the maximum amount you can take.
bestHouseBuild(houses)
Input format: space-separated non-negative integers.
[2, 3, 2] // → 3 (can't take both ends; best is the middle)
[1, 2, 3, 1] // → 4 (houses 1 and 3)
[5] // → 5
Start with the simpler version: houses in a line, no wraparound, no two adjacent. That's the classic house-robber pattern, worth understanding first since the circular version builds on it directly.
At each house: take it, meaning the preceding house wasn't taken, so the total is this house's value plus the best from two positions back; or skip it, meaning the total is just the best from one position back. Take the better option at each step. Since each step only needs the previous one or two best totals, a running pair of values suffices — O(1) extra space instead of a full DP array.
Now the first and last houses are also adjacent — can't take both. This breaks the simple left-to-right recurrence, since the decision about the last house depends on the first, and vice versa — a circular dependency the linear scan alone can't resolve.
Any valid selection either includes the first house or doesn't. Not including it: the first house is irrelevant and the last has no conflict left — a pure linear problem on houses 2 through n. Including it: the last house is definitely excluded — a pure linear problem on houses 1 through n-1.
Since every valid selection falls into exactly one of these cases, the max over both, each solved with the ordinary linear technique, gives the correct circular answer. Splitting a circle at the problematic seam into two overlapping linear problems, solving each simply, then combining, is a common technique for single-wraparound constraints.
A single house has no self-conflict — handled as a special case. Each linear subproblem is O(n) time, O(1) space, so the overall solution stays O(n) time, O(1) space despite the added circular constraint.
def best_house_build(houses):
n = len(houses)
if n == 0:
return 0
if n == 1:
return houses[0]
def rob_linear(arr):
prev = 0
curr = 0
for v in arr:
take = max(prev + v, curr)
prev = curr
curr = take
return curr
return max(rob_linear(houses[:n - 1]), rob_linear(houses[1:]))
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.