House Robber II

Unique Paths II

Min Cost Climbing Stairs

Maximize the loot from houses arranged in a circle where robbing two adjacent houses triggers the alarm.

You are a robber planning to loot houses along a street, but here the houses are arranged in a **circle**, so the first and last houses are adjacent. Each house holds `nums[i]` dollars, and robbing two directly adjacent houses on the same night triggers the alarm.

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

**Input / output**
- Input: `nums: int[]`
- Output: `int` (maximum loot)

**Examples**
1. `nums = [2,3,2]` returns `3` because houses `0` and `2` are adjacent, so you can only take the single house holding `3`.
2. `nums = [1,2,3,1]` returns `4` by robbing houses `0` and `2` (`1 + 3`).
3. `nums = [0]` returns `0`.

**Constraints**
- `1 <= nums.length <= 100`
- `0 <= nums[i] <= 1000`

**Follow-up**
The only wrinkle versus the linear House Robber is the wrap-around adjacency. Can you reuse the linear solution as a black box instead of writing a new circular recurrence?

- In the linear House Robber you may take any non-adjacent subset.
- Here house `0` and house `n-1` are neighbors too, so you can never rob both of them.
- A single house is a special case: just return it.

Why the circle matters

- Either you skip the last house or you skip the first house (you cannot keep both).
- So the answer is the better of robbing houses `0..n-2` and robbing houses `1..n-1`, each solved as an ordinary linear House Robber.
- Here is a first version that fills an explicit DP array for each range.

Split into two linear problems

- The linear recurrence `best[i] = max(best[i-1], best[i-2] + arr[i])` only needs the previous two results.
- Replace the DP array with two rolling variables and reuse that helper on both ranges.

Collapse the linear pass to O(1) space

- `robRange` scans a slice keeping `prevOne` and `prevTwo`.
- Call it on `nums[:-1]` and `nums[1:]`, then take the maximum. Handle the length-1 street before slicing so neither range becomes empty in a way that drops the only house.

Optimal two-pass solution

Trace `nums = [1,2,3,1]`.

- Range `[1,2,3]` (drop the last house): best loot is `4` by robbing `1` and `3`.
- Range `[2,3,1]` (drop the first house): best loot is `3` (either `3` alone or `2 + 1`).
- Answer is `max(4, 3) = 4`.

Dry run

- Forgetting the length-1 case and slicing into two empty ranges, which returns `0` instead of the single house.
- Trying to write one circular recurrence with a flag; the two-pass reduction is simpler and less error-prone.
- Double-counting by allowing both house `0` and house `n-1`.
- Follow-up: how would you also return *which* houses were robbed, not just the total?

Common mistakes and follow-ups

- One house: return it directly.
- Two houses: they are adjacent on both sides, so take the larger.
- The wrap neighbor can make a locally greedy pick wrong, so always compare both ranges.

Edge cases to test mentally

Reduce the circle to two linear passes and keep only rolling state in each. Time is `O(n)` and extra space is `O(1)`.