House Robber II
The problem
Houses form a circle and have nonnegative amounts. Maximize the sum of chosen houses without choosing any neighbors, including the first and last together.
Example
[4, 1, 2, 7] → 8 by choosing 1 and 7
Need a hint?
Every valid answer excludes either the first house or the last.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Handle empty and single-house inputs directly. Run the linear house-robber recurrence on indices 0 through n−2 and separately on 1 through n−1. Return the larger result. Iterate over index ranges to keep auxiliary space constant.
Complexity
O(n) time and O(1) extra space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.