House Robber II

Houses are in a circle, so the first and last are adjacent. Return the maximum amount you can rob without robbing adjacent houses. A naive search over subsets is exponential.

Why this is worth learning

The extra circular edge only forbids choosing both endpoints. Every valid selection therefore belongs to at least one of two linear problems: exclude the first or exclude the last.

Before coding: one-minute experiment

Why does [2,3,2] yield 3 instead of 4? Why is a singleton [7] not reduced to an empty line?

Function signature

func RobII(nums []int) int

Inputs / outputs

• nums: money in each house.
• Return: maximum loot without adjacent picks.

Example

nums = [2,3,2]
Either take house 0 or 2, but not both.
Output: 3

Constraints

• 0 <= len(nums) <= 100_000
• House amounts are nonnegative, and the maximum obtainable circular robbery total is guaranteed to fit the target Go int.

Core idea (near-solution)

You cannot take both first and last. Solve two linear subproblems:

• Rob houses [0..n-2]
• Rob houses [1..n-1] Take the max of the two.

Invariant: each subproblem is the standard House Robber DP.

Algorithm (step-by-step)

1. Handle n=0 and n=1.
2. Compute robLine(nums[:n-1]) and robLine(nums[1:]).
3. Return the max.

Correctness sketch

For n>=2, a feasible circular selection cannot contain both indices 0 and n-1. If it omits the last, it is feasible in nums[:n-1]; if it omits the first, it is feasible in nums[1:]. Conversely every nonadjacent selection in either linear slice is valid on the circle because one endpoint is absent. The union of these two feasible families contains exactly all circular solutions, so the larger linear optimum is the circular optimum. Empty and singleton inputs require explicit handling: slicing away either endpoint of a singleton would incorrectly discard its only value.

Trace (hand walkthrough)

Example input:
nums = [2,3,2]
Either take house 0 or 2, but not both.
Output: 3

Walk:
- rob 0..1 -> max(2,3)=3
- rob 1..2 -> max(3,2)=3
- answer 3

Pitfalls to avoid

• Treating it as a linear street (would allow picking both ends).
• Forgetting small n edge cases.

Debugging lens

Test lengths 0,1,2 separately and a case whose best line solution uses both endpoints. Use nonnegative amounts, as intended by the existing single-house behavior, and keep totals representable.

Complexity

• Time: O(n).
• Extra space: O(1).

Implementation notes (Go)

• Reuse the linear robber helper with rolling variables.

Contract precision

A singleton returns its value; empty input returns 0. Every candidate in either linear subproblem is a feasible circular robbery total, so the nonnegative-value and maximum-total guarantees bound the intermediate additions too.

Reconstruction checkpoint

Why does [2,3,2] yield 3 instead of 4? Why is a singleton [7] not reduced to an empty line?

Return to 1D DP (Including Kadane) · Module quiz