DSA House Robber II

The problem

House Robber II places houses in a circle. Robbing two neighbouring houses triggers an alarm, and in a circle the first and last houses are neighbours too.

Each house holds a known amount of money. No two robbed houses may be neighbours. The answer is the largest total that a legal plan can take.

cases = [
    ([2, 3, 2], 3),
    ([1, 2, 3, 1], 4),
    ([5, 1, 1, 5], 6),
    ([7], 7),
    ([9, 5], 9),
]
for houses, expected in cases:
    print("circle", houses, "best total:", expected)

The last two rows show the circle rule at its smallest. One house is taken alone. Two houses in a circle are neighbours, so only the richer one is taken.

Intuition: the straight-street answer overcounts

The first idea solves the list as a straight street. On a street the two end houses are far apart, so a plan may take both ends. The circle joins those ends and bans exactly that plan.

def rob_line(houses):
    best = 0
    skip_one = 0
    for money in houses:
        take = money + skip_one
        best, skip_one = max(best, take), best
    return best

houses = [5, 1, 1, 5]
print("both ends together:", houses[0] + houses[-1])
print("street answer:", rob_line(houses))
print("circle answer:", 6)

The street plan takes both 5 houses for 10. Those two houses stand next to each other in the circle. The plan is illegal here, and the true answer is 6.

Brute force: test every set of houses

The brute force tests every set of houses. It rejects a set when two chosen houses are neighbours, including the wrap-around pair of first and last. It keeps the largest total among the legal sets.

houses = [1, 2, 3, 1]
n = len(houses)
checked = 0
best = 0
for mask in range(2 ** n):
    checked += 1
    chosen = [i for i in range(n) if mask & (1 << i)]
    legal = True
    for i in chosen:
        if (i + 1) % n in chosen:
            legal = False
    if legal:
        best = max(best, sum(houses[i] for i in chosen))
print("sets checked:", checked)
print("best total:", best)

Four houses give 16 sets. Each added house doubles the set count. Most sets are illegal or poor, and the brute force sums them all anyway.

The optimal solution: solve two straight streets

Every legal circle plan misses the last house or misses the first house, so it is a legal plan on one of two straight streets. That one sentence is the whole method.

Case one drops the last house and solves that street. Case two drops the first house and solves that street. The larger of the two totals is the circle answer. A single house is answered on its own, before any split.

def rob_line(houses):
    best = 0
    skip_one = 0
    for money in houses:
        take = money + skip_one
        best, skip_one = max(best, take), best
    return best

def rob_circle(houses):
    if len(houses) == 1:
        return houses[0]
    return max(rob_line(houses[:-1]), rob_line(houses[1:]))

cases = [
    ([2, 3, 2], 3),
    ([1, 2, 3, 1], 4),
    ([5, 1, 1, 5], 6),
    ([7], 7),
    ([9, 5], 9),
]
for houses, expected in cases:
    result = rob_circle(houses)
    print("circle", houses, "->", result, "expected:", expected, "match:", result == expected)

All five cases match. The single house never reaches the split, because dropping either end of a one-house circle drops the house itself.

Walkthrough: the circle [1, 2, 3, 1]

Case one drops the last house and walks the street 1, 2, 3. Each line prints the take option, the skip option, and the best total after that house. The take option adds the house to the best total that skipped its neighbour.

def rob_line_trace(houses):
    best = 0
    skip_one = 0
    for money in houses:
        take = money + skip_one
        print("house", money, "- take:", take, "skip:", best, end=" ")
        best, skip_one = max(best, take), best
        print("best:", best)
    return best

print("drop last, street [1, 2, 3]:")
case_one = rob_line_trace([1, 2, 3])
print("drop first, street [2, 3, 1]:")
case_two = rob_line_trace([2, 3, 1])
print("case one:", case_one, "case two:", case_two)
print("circle answer:", max(case_one, case_two))

Case one ends at 4, from the houses holding 1 and 3. Case two ends at 3. The circle answer is the larger total, 4.

Complexity

Time is O(n) for n houses. The solver walks each street once, and the two streets together visit each house at most twice.

Space is O(1). Each walk keeps two running totals and nothing else.

def rob_line_count(houses):
    best = 0
    skip_one = 0
    visits = 0
    for money in houses:
        visits += 1
        take = money + skip_one
        best, skip_one = max(best, take), best
    return best, visits

for n in [4, 8, 16]:
    houses = [1] * n
    _, v1 = rob_line_count(houses[:-1])
    _, v2 = rob_line_count(houses[1:])
    print("houses", n, "- visits across both cases:", v1 + v2)

The visits grow in a straight line with the house count, two short of double. No table is stored, and no set is ever enumerated.

Edge cases and pitfalls

An empty circle answers 0. Two houses answer the larger single amount, because the pair are neighbours twice over in a circle of two.

def rob_line(houses):
    best = 0
    skip_one = 0
    for money in houses:
        take = money + skip_one
        best, skip_one = max(best, take), best
    return best

def rob_circle(houses):
    if len(houses) == 1:
        return houses[0]
    return max(rob_line(houses[:-1]), rob_line(houses[1:]))

print("empty circle:", rob_circle([]))
print("one house:", rob_circle([7]))
print("two houses:", rob_circle([9, 5]))
print("two equal houses:", rob_circle([3, 3]))
print("all zeros:", rob_circle([0, 0, 0]))

Splitting a single house is the quiet pitfall. Dropping its last house and dropping its first house both leave an empty street. Without the special case, one house worth 7 would answer 0.

def rob_line(houses):
    best = 0
    skip_one = 0
    for money in houses:
        take = money + skip_one
        best, skip_one = max(best, take), best
    return best

houses = [7]
print("drop last street:", houses[:-1], "answer:", rob_line(houses[:-1]))
print("drop first street:", houses[1:], "answer:", rob_line(houses[1:]))
print("correct answer:", houses[0])

The both-ends mistake overcounts, and the single-house split undercounts. The case split plus the one-house special case avoids both errors.