House Robber II – Solution & Complexity

• 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.

• 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.

• 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.

• 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.

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.

• 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?

• 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.

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