# House Robber

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

## 1. Core Invariant / The Trick

At house `x`, either skip (`rob2`) or rob `x` + best two houses back (`rob1 + x`). Recurrence `nxt = max(rob2, rob1 + x)` collapses strictly into two rolling variables.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Single linear pass updating two variables representing `dp[i-2]` and `dp[i-1]`.

## 3. Minimal Idiomatic Code

### Python
```python
def rob(nums: list[int]) -> int:
    rob1 = rob2 = 0
    for x in nums:
        rob1, rob2 = rob2, max(rob2, rob1 + x)
    return rob2
```

### TypeScript
```typescript
export function rob(nums: number[]): number {
  let rob1 = 0, rob2 = 0;
  for (const x of nums) {
    [rob1, rob2] = [rob2, Math.max(rob2, rob1 + x)];
  }
  return rob2;
}
```

### C++
```cpp
int rob(vector<int>& nums) {
    int rob1 = 0, rob2 = 0;
    for (int x : nums) { int nxt = max(rob2, rob1 + x); rob1 = rob2; rob2 = nxt; }
    return rob2;
}
```

### Java
```java
int rob(int[] nums) {
    int rob1 = 0, rob2 = 0;
    for (int x : nums) { int nxt = Math.max(rob2, rob1 + x); rob1 = rob2; rob2 = nxt; }
    return rob2;
}
```

### Go
```go
func rob(nums []int) int {
    rob1, rob2 := 0, 0
    for _, x := range nums { rob1, rob2 = rob2, max(rob2, rob1+x) }
    return rob2
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Greedily choosing odd vs even indices fails `[2, 1, 1, 2] -> 4`.

### Follow-ups
- House Robber II wraps around on a circle by taking `max(robLinear(nums[1:]), robLinear(nums[:-1]))`.