House Robber II

Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses are arranged in a circle. This means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses are broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Examples

Constraints

• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 1000

Deconstructing the Circular Dependency into Linear Arrays

The circle constraint means we cannot rob both the first house (nums[0]) and the last house (nums[n - 1]). If we choose to rob nums[0], we must skip nums[n - 1]. If we choose to rob nums[n - 1], we must skip nums[0].

This allows us to break the circular problem into two linear subproblems:

1. Run the standard “House Robber” algorithm on nums[0..n-2] (ignoring the last house).
2. Run the same algorithm on nums[1..n-1] (ignoring the first house).

The final answer is simply the maximum of these two linear runs. If the input contains only one house, we return its value immediately without running the subproblems.

Solution 1: Splitting Subarrays (Constant Space)

Re-use the O(1) space linear House Robber algorithm, executing it twice on slices of the input.

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        // choose maximum between robbing without the last house or without the first
        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 robPrev2 = 0;
        int robPrev1 = 0;

        for (int i = start; i <= end; i++) {
            int current = Math.max(nums[i] + robPrev2, robPrev1);
            robPrev2 = robPrev1;
            robPrev1 = current;
        }
        return robPrev1;
    }
}

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

        def rob_linear(start, end):
            rob_prev2 = 0
            rob_prev1 = 0
            for i in range(start, end + 1):
                current = max(nums[i] + rob_prev2, rob_prev1)
                rob_prev2 = rob_prev1
                rob_prev1 = current
            return rob_prev1

        # choose maximum between robbing without the last house or without the first
        return max(rob_linear(0, len(nums) - 2), rob_linear(1, len(nums) - 1))

#include <vector>
#include <algorithm>

class Solution {
private:
    int robLinear(const std::vector<int>& nums, int start, int end) {
        int robPrev2 = 0;
        int robPrev1 = 0;

        for (int i = start; i <= end; i++) {
            int current = std::max(nums[i] + robPrev2, robPrev1);
            robPrev2 = robPrev1;
            robPrev1 = current;
        }
        return robPrev1;
    }

public:
    int rob(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];

        // choose maximum between robbing without the last house or without the first
        return std::max(robLinear(nums, 0, nums.size() - 2),
                        robLinear(nums, 1, nums.size() - 1));
    }
};

Complexity Analysis:

• Time Complexity: O(n). We run two linear scans of size n - 1.
• Space Complexity: O(1) auxiliary space as we do not copy array elements.

Where it breaks: If the input array has only one house, the indices for both slices become invalid (0 to -1 for the first slice). You must handle the single-element case explicitly as a base guard.

Common Mistakes

• Failing to handle the single-node base case. Calling slice index operations on a single-element array results in out of bounds errors or incorrect results.
• Copying array slices unnecessarily. Instead of duplicating subarray elements in memory (which uses O(n) space), pass start and end indices to a helper function.
• Attempting to solve using a single pass with state bits. Tracking whether the first node was robbed in a single pass is highly complex and error-prone compared to running the algorithm twice on slices.

Frequently Asked Questions

Why does running the algorithm twice on slices work? Because the first and last houses cannot both be robbed, any optimal selection must exclude either the first house, the last house, or both. Slicing ensures we evaluate all valid configurations.

Can we solve this recursively with memoization? Yes. You can write a recursive DFS with a cache, passing the current index and a flag indicating if the first house was robbed, but the iterative slicing method is simpler.

What does this problem test in interviews? It tests your ability to break circular dependency structures into linear subproblems, preventing complex boundary conditions.

← All Problems