The problem
Same as House Robber, but the houses are arranged in a circle, so the first and the last house are also neighbours.
Input: [2, 3, 2, 6, 4] Output: 9 (3 + 6)
Picture it
Picture the houses around a roundabout. Because the first and last touch, you can never rob both. So solve two ordinary straight streets: one without the first house and one without the last house. The better of the two answers is the best for the circle.
How to recognise it
- It is House Robber (no two neighbours) with one twist: the houses form a circle, so the first and last are also neighbours.
- The circular rule is a conflict between two specific ends, not a new kind of problem. Break it by deciding which end you may use.
- Up to 100 houses (money at most 1,000) makes trying every subset (2^100) impossible.
- Whenever a circle or ring reduces to "line problem, solved twice", look for a way to cut the circle at its seam.
Start with brute force
Try every subset of houses, keep those where no two robbed houses sit next to each other (including house 0 next to the last house), and take the largest total.
def rob_circle_brute(houses):
n = len(houses)
best = 0
for mask in range(1 << n):
picked = [i for i in range(n) if mask >> i & 1]
ok = all(b - a > 1 for a, b in zip(picked, picked[1:]))
if ok and n > 1 and 0 in picked and n - 1 in picked:
ok = False
if ok:
best = max(best, sum(houses[i] for i in picked))
return best
There are 2^n subsets and each is checked in O(n), so time is O(n × 2^n); for 100 houses that is about 10^32 operations. Space is O(n) for the picked list.
From brute force to the idea
- Find the conflict. On a line you solve this with two running values. The circle adds only one new rule: house 0 and house n − 1 cannot both be robbed.
- Cut the circle. Either you do not rob the first house, or you do not rob the last (or neither). Those cases cover every valid plan.
- Two line problems. If the first house is off limits, the rest
houses[1:]is an ordinary street. If the last is off limits,houses[:-1]is an ordinary street. Solve each with the House Robber loop. - Combine. Return the larger of the two. A plan that skips both ends is counted in both, which is harmless.
- One house is special. With a single house the two slices are both empty and would give 0, so the code returns
houses[0]directly.
This is the key idea: break the circle into two straight streets, one without the first house and one without the last, and take the better.
The key idea
answer = max(rob(houses[1:]), rob(houses[:-1])). Two linear passes.
Python solution
def rob_circle(houses):
if len(houses) == 1:
return houses[0]
def rob_line(hs):
skip, take = 0, 0
for loot in hs:
skip, take = max(skip, take), skip + loot
return max(skip, take)
return max(rob_line(houses[1:]), # leave the first house alone
rob_line(houses[:-1])) # or leave the last oneIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n × 2^n): every subset is checked in O(n) | O(n): the picked list |
| Two line passes (shown code) | O(n): two passes of the two-variable loop (plus O(n) to copy the slices) | O(n): the two slices (the loop itself uses O(1)) |
Edge cases
- One house (
[5]): returns5. Without thelen == 1check it would return0. - Two houses (
[2, 3]): returns3; they are neighbours, so take the larger. - Three houses (
[2, 3, 2]): returns3. Robbing both 2s is forbidden because they are neighbours on the circle; a straight street would allow 4. - Example
[1, 2, 3, 1]: returns4. - Example
[2, 7, 9, 3, 1]: returns11, not 12 (the 2 and 1 cannot both be used with the 9). - No houses (
[]): returns0, because both slices are empty. The problem never asks for it.
Common mistakes
- Running the straight-street solver on the whole list:
[1, 2, 3]gives 4, but 1 and 3 are neighbours on the circle, so the answer is 3. - Forgetting the single-house case, which makes
[5]return 0. - Cutting only one end (just
houses[1:]), which can lose a plan that uses the first house. - Writing the loop twice with copied code and changing one copy by accident. A helper function (as in the shown code) avoids this.
On a straight street (not a circle) you must rob house 0, for example because it holds the key to the others. After that no two neighbours may be robbed. Find the most money, with at least one house. For [2, 7, 9, 3, 1] the answer is 12 (2 + 9 + 1). Describe your approach, then write it if you like.
Compare with our answer
Forcing house 0 removes it and its neighbour from the choice, so the rest is a plain House Robber on houses[2:].
def rob_first_forced(houses):
def rob_line(hs):
skip, take = 0, 0
for loot in hs:
skip, take = max(skip, take), skip + loot
return max(skip, take)
if not houses:
return 0
return houses[0] + rob_line(houses[2:])
rob_first_forced([2, 7, 9, 3, 1]) is 12 and rob_first_forced([5, 100]) is 5. Time O(n), space O(n) for the slice.
A strong answer mentions: forcing a choice removes the neighbour too, reducing the problem to a smaller line, the same idea of turning a constraint into a shorter ordinary problem used for the circle, and the one-house case returning houses[0].
1. Gas stations sit on a ring road. You may take the fuel from stations, but never two adjacent stations (the last and first count as adjacent), and you want the largest total. Which approach fits best?
Any valid plan leaves out the first or the last station, so two straight-line solves cover all plans. One straight solve may take both ends, and the rotation and sorting ideas are greedy and can miss better combinations.
2. What is the cost of the shown solution, and where does the extra space come from?
Each line solve is a single pass, and houses[1:] and houses[:-1] copy the list. The loop alone uses two variables, but the slices make the total O(n). No sorting or pair checking happens.
3. A learner deletes the if len(houses) == 1: return houses[0] check. Which input now gives a wrong answer?
For [5] both slices are empty, so the function returns 0 instead of 5. For the other inputs each slice still contains a house, and the results (3, 3 and 11) stay correct.
Score 60% or more and the lesson is marked complete.