Problem 56 · Dynamic Programming

House Robber II

MediumClassic DSA & systems

01Problem

Houses are arranged in a circle; adjacent houses cannot both be robbed. Given each house's money, return the maximum amount you can rob.

02Key insight

The circle only means house 0 and house n-1 can't both be taken: solve the linear problem on nums[1:] and nums[:-1] and take the max.

03Solution

solution.pypython10 lines

def rob_linear(nums: list[int]) -> int:
    take, skip = 0, 0
    for x in nums:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)

def rob(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]
    return max(rob_linear(nums[1:]), rob_linear(nums[:-1]))

Try it first.

TimeO(n)

SpaceO(n) for slices (O(1) with index ranges)

tests.py · 4 passing

tests.pypython4 lines

assert rob([2,3,2]) == 3
assert rob([1,2,3,1]) == 4
assert rob([5]) == 5
assert rob([1,2,3]) == 3

04Staff-level follow-up

Houses form a tree (House Robber III)? Post-order DFS returning (rob_this, skip_this) per node, still O(n).