House Robber II

How it works

This is House Robber II, where houses are arranged in a circle.
Because of the circular setup, you cannot rob both the first and last house.

To handle this, split the problem into two linear subproblems:

1. Rob houses excluding the first house.
2. Rob houses excluding the last house.

Each subproblem becomes the classic House Robber I, which can be solved using two variables instead of a full DP array.

Steps

1. If there is only one house, return its value.
2. Compute the maximum money for:
   • Houses nums[1:] (skip first)
   • Houses nums[:-1] (skip last)
3. For each linear list:
   • Maintain two variables:
     • rob1 -> best up to house i-2
     • rob2 -> best up to house i-1
   • For each house:

Complexity

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

Things to watch for

Forgetting the Single House Edge Case

When there is only one house, the circular constraint does not apply since there is no adjacency conflict. If you split the problem into nums[1:] and nums[:-1] without handling this case, both subarrays become empty when n=1, and the function returns 0 instead of nums[0]. Always check if the array has only one element and return its value directly.

Incorrectly Handling the Circular Constraint

The key insight is that the first and last houses cannot both be robbed. A common mistake is to add complex flag logic throughout the recursion when a simpler approach exists: run the standard House Robber algorithm twice, once excluding the first house and once excluding the last house. Taking the maximum of these two results correctly handles the circular dependency without overcomplicating the code.

Off-by-One Errors in Array Slicing

When splitting the array into nums[1:] (exclude first) and nums[:-1] (exclude last), be careful with language-specific slicing syntax. In some languages, you need to manually copy subarrays or adjust loop bounds. An off-by-one error here can lead to including both the first and last houses in one subproblem, or excluding more houses than intended, producing incorrect results.

from typing import List

class Solution:

    def rob(self, nums: List[int]) -> int:
        return max(nums[0], self.helper(nums[1:]),
                            self.helper(nums[:-1]))

    def helper(self, nums):
        rob1, rob2 = 0, 0

        for num in nums:
            newRob = max(rob1 + num, rob2)
            rob1 = rob2
            rob2 = newRob
        return rob2

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> nums1(nums.begin() + 1, nums.end());
        vector<int> nums2(nums.begin(), nums.end() - 1);
        return max(nums[0],
               max(helper(nums1), helper(nums2)));
    }

private:
    int helper(vector<int>& nums) {
        int rob1 = 0, rob2 = 0;
        for (int num : nums) {
            int newRob = max(rob1 + num, rob2);
            rob1 = rob2;
            rob2 = newRob;
        }
        return rob2;
    }
};