# House Robber II

- **Canonical ID**: `house-robber-ii`
- **Canonical URL**: https://dsacheatsheet.com/problems/house-robber-ii
- **Difficulty**: medium
- **Patterns**: 1D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/house-robber-ii/

## 1. Core Invariant / The Trick

Since house `0` and `n-1` are adjacent in a circle, they cannot both be robbed. Split into two linear House Robber subproblems excluding either endpoint: `max(nums[0], linear(nums[:-1]), linear(nums[1:]))`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Two linear passes over `N - 1` slices in O(1) space.

## 3. Minimal Idiomatic Code

### Python
```python
def rob(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]
    def lin(arr):
        a = b = 0
        for x in arr:
            a, b = b, max(b, a + x)
        return b
    return max(lin(nums[:-1]), lin(nums[1:]))
```

### TypeScript
```typescript
export function rob(nums: number[]): number {
  if (nums.length === 1) return nums[0];
  const lin = (l: number, r: number) => {
    let a = 0, b = 0;
    for (let i = l; i < r; i++) [a, b] = [b, Math.max(b, a + nums[i])];
    return b;
  };
  return Math.max(lin(0, nums.length - 1), lin(1, nums.length));
}
```

### C++
```cpp
int rob(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    auto lin = [&](int l, int r) {
        int a = 0, b = 0;
        for (int i = l; i < r; ++i) { int t = max(b, a + nums[i]); a = b; b = t; }
        return b;
    };
    return max(lin(0, nums.size() - 1), lin(1, nums.size()));
}
```

### Java
```java
int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    return Math.max(lin(nums, 0, nums.length - 1), lin(nums, 1, nums.length));
}
int lin(int[] a, int l, int r) {
    int p1 = 0, p2 = 0;
    for (int i = l; i < r; i++) { int t = Math.max(p2, p1 + a[i]); p1 = p2; p2 = t; }
    return p2;
}
```

### Go
```go
func rob(nums []int) int {
    if len(nums) == 1 { return nums[0] }
    lin := func(s []int) int {
        a, b := 0, 0
        for _, x := range s { a, b = b, max(b, a+x) }
        return b
    }
    return max(lin(nums[:len(nums)-1]), lin(nums[1:]))
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Length-1 array (`[5]`): slicing `nums[:-1]` and `nums[1:]` both yield empty `[]`, returning `0` unless guarded by `if len(nums) == 1: return nums[0]`.

### Follow-ups
- House Robber III solves the same non-adjacent constraint on a Binary Tree.