LeetCode #213 Medium

House Robber II

Same as House Robber, but the houses are arranged in a circle — the first and last are now adjacent. Return the maximum loot.

dynamic-programmingarray

Open on LeetCode ↗

02

Intuition

💡

The circle adds exactly one new constraint: houses 0 and n-1 cannot both be robbed. Rather than inventing a circular DP, notice what that constraint implies — any optimal solution either leaves out the first house or leaves out the last one (possibly both). So run the linear House Robber solver twice, once on nums[0..n-2] and once on nums[1..n-1], and take the better result. Each window is a plain line with no wraparound, so the original algorithm applies untouched.

03

Approach

1

Isolate what actually changed

House Robber II is House Robber plus one adjacency: 0 and n-1 are neighbours. Every other constraint is identical. Rewriting the DP to handle wraparound means threading a 'did I take the first house?' flag through every state, doubling the state space for one edge — a lot of machinery for a small change.

2

Split the one hard constraint into two easy problems

The new rule forbids taking both endpoints, so any valid solution falls into one of two overlapping cases: it omits house 0, or it omits house n-1. The optimum is in at least one of them. Case A is the linear problem on nums[1..n-1]; case B is the linear problem on nums[0..n-2]. Both windows are ordinary lines. Solutions omitting both endpoints are counted in both cases, which is harmless — we take a maximum, not a sum.

3

Run the linear solver twice and take the max

Call the House Robber routine on each window and return the larger answer. Two O(n) passes with O(1) space each. The only case needing care is n == 1, where one of the windows is empty — handle it up front by returning nums[0]. This reduce-to-a-solved-problem move is worth naming explicitly in an interview.

04

Solution & live demo

python

▶1class Solution:
▶2    def rob(self, nums):
▶3        if len(nums) == 1:
▶4            return nums[0]
▶5 
▶6        def line(a):
▶7            take, skip = 0, 0
▶8            for x in a:
▶9                take, skip = skip + x, max(skip, take)
▶10            return max(take, skip)
▶11 
▶12        return max(line(nums[:-1]), line(nums[1:]))

05

Edge cases

Single house

Both windows would be empty, so return nums[0] before splitting. The circular constraint has nothing to act on with one house.

Two houses

The windows are [nums[0]] and [nums[1]], giving max(nums[0], nums[1]) — correct, since they are adjacent both ways round.

Three houses

Only one house can ever be robbed, and taking the maximum over the two windows finds the largest.

Optimal solution omits both endpoints

It appears in both windows and is returned by whichever is larger; no double-counting occurs because we take a max.

06

Complexity

Time

O(n)

Space

O(1)

Two linear passes over slices of the array, each using two rolling variables. The slices can be avoided with index bounds if the extra O(n) copy matters.