LeetCode 213: House Robber II

Problem Restatement

We are given an integer array nums.

Each nums[i] represents the amount of money in house i.

We want to rob houses without robbing two adjacent houses.

The difference from the first House Robber problem is that the houses are arranged in a circle. That means the first house and the last house are also adjacent.

Return the maximum amount of money we can rob without alerting the police.

The official statement says the houses are arranged in a circle, so the first house is the neighbor of the last one, and adjacent robbed houses trigger the security system. Given nums, return the maximum amount we can rob tonight without alerting the police.

Input and Output

Example function shape:

def rob(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [2, 3, 2]

We cannot rob both 2s because the first and last houses are adjacent.

Best choice:

rob house 1
money = 3

Answer:

3

Example 2:

nums = [1, 2, 3, 1]

Best choice:

rob house 0 and house 2
money = 1 + 3 = 4

Answer:

4

Example 3:

nums = [1, 2, 3]

Because the houses are circular:

house 0 is adjacent to house 2

We cannot rob 1 and 3 together.

Best choice:

rob house 2
money = 3

Answer:

3

First Thought: Use House Robber I

For a normal line of houses, the recurrence is:

best at current house = max(skip current, rob current)

If we process a linear array, we can keep two values:

For each house value money:

current = max(prev1, prev2 + money)

Then shift the values forward.

This solves the linear version.

Problem With Direct Linear DP

In this problem, the first and last houses are adjacent.

So a normal linear DP may choose both:

nums = [2, 3, 2]

Linear DP might consider robbing:

house 0 and house 2

for total:

4

But that is invalid because house 0 and house 2 are neighbors in the circle.

We need to break the circular dependency.

Key Insight

Since the first and last houses are adjacent, we cannot rob both.

So every valid answer belongs to one of these two cases:

Then each case becomes the normal linear House Robber problem.

Final answer:

max(
    rob_linear(nums[1:]),
    rob_linear(nums[:-1]),
)

We also need to handle the single-house case separately.

Algorithm

1. If len(nums) == 1, return nums[0].
2. Solve the linear robbery problem on nums[0:n-1].
3. Solve the linear robbery problem on nums[1:n].
4. Return the larger result.

Linear Helper

For a linear list of houses, use:

prev2 = 0
prev1 = 0

For each amount money:

current = max(prev1, prev2 + money)

Meaning:

Then update:

prev2 = prev1
prev1 = current

At the end, prev1 is the best answer.

Walkthrough

Use:

nums = [1, 2, 3, 1]

Because the houses are circular, split into two cases.

Case 1: exclude the last house.

[1, 2, 3]

Best linear robbery:

rob 1 and 3
total = 4

Case 2: exclude the first house.

[2, 3, 1]

Best linear robbery:

rob 2 and 1
total = 3

Take the maximum:

max(4, 3) = 4

Answer:

4

Correctness

Any valid robbery plan cannot include both the first house and the last house, because those two houses are adjacent in the circle.

Therefore every valid plan must fall into at least one of these two groups:

1. plans that exclude the first house
2. plans that exclude the last house

The algorithm solves both groups as ordinary linear House Robber problems.

For each linear subproblem, the helper is correct because at every house there are exactly two choices:

• skip the current house, keeping the best value from the previous house
• rob the current house, adding its money to the best value from two houses before

Taking the maximum of these two choices gives the best value up to the current position.

Since the circular problem is fully covered by the two linear cases, and each linear case is solved optimally, the maximum of the two results is the optimal answer for the circular problem.

Complexity

The implementation below avoids creating slices, so extra space stays constant.

Implementation

class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)

        if n == 1:
            return nums[0]

        return max(
            self.rob_linear(nums, 0, n - 2),
            self.rob_linear(nums, 1, n - 1),
        )

    def rob_linear(self, nums: list[int], start: int, end: int) -> int:
        prev2 = 0
        prev1 = 0

        for i in range(start, end + 1):
            current = max(prev1, prev2 + nums[i])
            prev2 = prev1
            prev1 = current

        return prev1

Code Explanation

Handle the single-house case first:

if n == 1:
    return nums[0]

This is necessary because excluding either the first or last house would leave an empty range.

Then solve two linear cases:

self.rob_linear(nums, 0, n - 2)
self.rob_linear(nums, 1, n - 1)

The first excludes the last house.

The second excludes the first house.

Return the better one:

return max(...)

Inside rob_linear, initialize:

prev2 = 0
prev1 = 0

For each house:

current = max(prev1, prev2 + nums[i])

prev1 means skipping this house.

prev2 + nums[i] means robbing this house.

Then update the rolling DP state:

prev2 = prev1
prev1 = current

Finally:

return prev1

Simpler Slice Version

This version is shorter, but it creates sliced lists.

class Solution:
    def rob(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        return max(
            self.rob_linear(nums[:-1]),
            self.rob_linear(nums[1:]),
        )

    def rob_linear(self, houses: list[int]) -> int:
        prev2 = 0
        prev1 = 0

        for money in houses:
            current = max(prev1, prev2 + money)
            prev2 = prev1
            prev1 = current

        return prev1

The index-range version is slightly more memory-efficient.

Testing

def run_tests():
    s = Solution()

    assert s.rob([2, 3, 2]) == 3
    assert s.rob([1, 2, 3, 1]) == 4
    assert s.rob([1, 2, 3]) == 3
    assert s.rob([5]) == 5
    assert s.rob([1, 2]) == 2
    assert s.rob([2, 7, 9, 3, 1]) == 11

    print("all tests passed")

run_tests()