House Robber II

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbors.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

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

You cannot rob nums[0] + nums[2] = 6 because nums[0] and nums[2] are adjacent houses. The maximum you can rob is nums[1] = 4.

You cannot rob nums[0] + nums[2] + nums[4] = 16 because nums[0] and nums[4] are adjacent houses. The maximum you can rob is nums[1] + nums[4] = 15.

Approach

Because the houses form a circle, you cannot rob both the first and last. Compute the best result for two linear ranges: nums[0..n-2] and nums[1..n-1], and take the max. Use the same linear DP as House Robber I.

Why It Works

Any optimal solution either robs the first house or the last, but not both. Splitting into the two exclusive cases covers all valid solutions. The linear DP is optimal for each case, so the maximum of the two is optimal for the circle.

Complexity

• Time: O(n)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def rob_range(arr: List[int]) -> int:
            prev2 = 0
            prev1 = 0
            for num in arr:
                prev2, prev1 = prev1, max(prev1, prev2 + num)
            return prev1

        return max(rob_range(nums[:-1]), rob_range(nums[1:]))