LeetCode 213 · 1-D DP

House Robber II, explained with a picture

Houses around a roundabout.

Medium1-D DP
▶ Watch it step by step

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

  1. 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.
  2. 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.
  3. 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.
  4. Combine. Return the larger of the two. A plan that skips both ends is counted in both, which is harmless.
  5. 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 one

In 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

ApproachTimeSpace
Brute forceO(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]): returns 5. Without the len == 1 check it would return 0.
  • Two houses ([2, 3]): returns 3; they are neighbours, so take the larger.
  • Three houses ([2, 3, 2]): returns 3. Robbing both 2s is forbidden because they are neighbours on the circle; a straight street would allow 4.
  • Example [1, 2, 3, 1]: returns 4.
  • Example [2, 7, 9, 3, 1]: returns 11, not 12 (the 2 and 1 cannot both be used with the 9).
  • No houses ([]): returns 0, 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.
Your turn: the first house is compulsory

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].

Check what stuck

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?

2. What is the cost of the shown solution, and where does the extra space come from?

3. A learner deletes the if len(houses) == 1: return houses[0] check. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.