# 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

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Maximum money that can be robbed |
| Constraint | Adjacent houses cannot both be robbed |
| Circular rule | House `0` and house `n - 1` are adjacent |

Example function shape:

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

## Examples

Example 1:

```python
nums = [2, 3, 2]
```

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

Best choice:

```text
rob house 1
money = 3
```

Answer:

```python
3
```

Example 2:

```python
nums = [1, 2, 3, 1]
```

Best choice:

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

Answer:

```python
4
```

Example 3:

```python
nums = [1, 2, 3]
```

Because the houses are circular:

```text
house 0 is adjacent to house 2
```

We cannot rob `1` and `3` together.

Best choice:

```text
rob house 2
money = 3
```

Answer:

```python
3
```

## First Thought: Use House Robber I

For a normal line of houses, the recurrence is:

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

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

| Variable | Meaning |
|---|---|
| `prev2` | Best result up to two houses before |
| `prev1` | Best result up to previous house |

For each house value `money`:

```python
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:

```python
nums = [2, 3, 2]
```

Linear DP might consider robbing:

```text
house 0 and house 2
```

for total:

```python
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:

| Case | Houses considered |
|---|---|
| Exclude first house | Rob only from index `1` to `n - 1` |
| Exclude last house | Rob only from index `0` to `n - 2` |

Then each case becomes the normal linear House Robber problem.

Final answer:

```python
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:

```python
prev2 = 0
prev1 = 0
```

For each amount `money`:

```python
current = max(prev1, prev2 + money)
```

Meaning:

| Choice | Value |
|---|---|
| Skip current house | `prev1` |
| Rob current house | `prev2 + money` |

Then update:

```python
prev2 = prev1
prev1 = current
```

At the end, `prev1` is the best answer.

## Walkthrough

Use:

```python
nums = [1, 2, 3, 1]
```

Because the houses are circular, split into two cases.

Case 1: exclude the last house.

```python
[1, 2, 3]
```

Best linear robbery:

```text
rob 1 and 3
total = 4
```

Case 2: exclude the first house.

```python
[2, 3, 1]
```

Best linear robbery:

```text
rob 2 and 1
total = 3
```

Take the maximum:

```python
max(4, 3) = 4
```

Answer:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan two linear ranges |
| Space | `O(1)` | Only a few variables are used |

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

## Implementation

```python
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:

```python
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:

```python
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:

```python
return max(...)
```

Inside `rob_linear`, initialize:

```python
prev2 = 0
prev1 = 0
```

For each house:

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

`prev1` means skipping this house.

`prev2 + nums[i]` means robbing this house.

Then update the rolling DP state:

```python
prev2 = prev1
prev1 = current
```

Finally:

```python
return prev1
```

## Simpler Slice Version

This version is shorter, but it creates sliced lists.

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `[2,3,2]` | First and last cannot both be robbed |
| `[1,2,3,1]` | Standard circular example |
| `[1,2,3]` | Best single high house due to circle |
| `[5]` | Single-house case |
| `[1,2]` | Two adjacent circular houses |
| `[2,7,9,3,1]` | Larger DP case |