Code Implementation

class Solution:
    def rob(self, nums):
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        def rob_linear(houses):
            prev, curr = 0, 0
            for num in houses:
                prev, curr = curr, max(curr, prev + num)
            return curr
        
        # Case 1: Do not rob the last house
        case1 = rob_linear(nums[:-1])
        # Case 2: Do not rob the first house
        case2 = rob_linear(nums[1:])
        return max(case1, case2)
      

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        
        return max(robLinear(nums, 0, nums.size() - 2),
                   robLinear(nums, 1, nums.size() - 1));
    }
    
private:
    int robLinear(const vector<int>& nums, int start, int end) {
        int prev = 0, curr = 0;
        for (int i = start; i <= end; ++i) {
            int temp = curr;
            curr = max(curr, prev + nums[i]);
            prev = temp;
        }
        return curr;
    }
};
      

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(robLinear(nums, 0, nums.length - 2),
                        robLinear(nums, 1, nums.length - 1));
    }
    
    private int robLinear(int[] nums, int start, int end) {
        int prev = 0, curr = 0;
        for (int i = start; i <= end; i++) {
            int temp = curr;
            curr = Math.max(curr, prev + nums[i]);
            prev = temp;
        }
        return curr;
    }
}
      

var rob = function(nums) {
    if (!nums.length) return 0;
    if (nums.length === 1) return nums[0];
    
    function robLinear(houses) {
        let prev = 0, curr = 0;
        for (let num of houses) {
            let temp = curr;
            curr = Math.max(curr, prev + num);
            prev = temp;
        }
        return curr;
    }
    
    // Exclude last house
    let case1 = robLinear(nums.slice(0, nums.length - 1));
    // Exclude first house
    let case2 = robLinear(nums.slice(1));
    return Math.max(case1, case2);
};
      

Problem Description

You are given an array nums where each element represents the amount of money stashed in a house arranged in a circle. The houses are adjacent, and if you rob two directly connected houses, the police will be alerted. Your task is to determine the maximum amount of money you can rob tonight without robbing any two adjacent houses. Because the houses are arranged in a circle, the first and last houses are also considered adjacent.

• Each house can only be robbed once.
• You cannot rob two adjacent houses (including the first and last house).
• Return a single integer representing the maximum amount of money you can rob.

Thought Process

At first glance, this problem looks similar to the classic "House Robber" problem, where houses are in a straight line. In that version, you can use dynamic programming to decide for each house whether to rob it or skip it, based on the best outcome so far.

However, the circular arrangement adds a twist: the first and last houses are now adjacent. This means you cannot simply apply the same logic to the entire array, because robbing the first house prevents you from robbing the last house, and vice versa.

The brute-force approach would try every possible combination, but that's not efficient. We need a smarter way—one that breaks the problem into manageable pieces. The key insight is to split the problem into two scenarios:

• Rob houses from the first to the second-to-last (excluding the last).
• Rob houses from the second to the last (excluding the first).

For each scenario, the problem reduces to the classic "House Robber" problem on a line, which we can solve efficiently.

Solution Approach

Let's break down the steps to solve the problem:

1. Handle Base Cases:
   • If there are no houses, return 0.
   • If there is only one house, return its value.
2. Divide the Problem:
   • Since the first and last houses are adjacent, you can't rob both.
   • So, consider two cases:
     • Rob from house 0 to house n-2 (exclude the last house).
     • Rob from house 1 to house n-1 (exclude the first house).
3. Solve Each Case Using Dynamic Programming:
   • For each subarray, use the classic "House Robber" DP approach:
     • For each house, decide: rob it (and add its value to the total two houses back), or skip it (carry forward the previous total).
     • Keep track of two variables: prev (total up to house i-2) and curr (total up to house i-1).
4. Return the Maximum:
   • The answer is the larger of the two cases above.

This approach ensures that we never rob both the first and last house, and leverages efficient dynamic programming for optimal performance.

Example Walkthrough

Let's walk through an example with nums = [2, 3, 2]:

• Case 1: Exclude the last house, so consider [2, 3].
• Apply the linear DP:
  • House 0: Rob = 2
  • House 1: Max of (Rob house 1: 3, or skip and keep previous: 2) → 3
• Maximum for this case: 3
• Case 2: Exclude the first house, so consider [3, 2].
• Apply the linear DP:
  • House 0: Rob = 3
  • House 1: Max of (Rob house 1: 2, or skip and keep previous: 3) → 3
• Maximum for this case: 3
• The final answer is the maximum of the two cases: 3.

This process ensures we never rob both the first and last house, and always get the best possible total.

Time and Space Complexity

Brute-force approach: Would try all valid combinations, leading to exponential time complexity: O(2ⁿ).

Optimized DP approach:

• For each of the two scenarios (excluding first or last house), we process all n houses once.
• Each scenario is solved in O(n) time, so total time complexity is O(n).
• We only use a constant amount of extra space (just a few variables), so space complexity is O(1).

Summary

The House Robber II problem builds on the classic dynamic programming approach, but adds the twist of a circular house arrangement. By smartly splitting the problem into two linear subproblems—each excluding either the first or last house—we avoid the adjacency issue and apply efficient DP. This leads to a solution that's both elegant and optimal, with linear time and constant space complexity.