Dynamic Programming: House Robber 2 (DP 6)

1. Overview and Problem Statement

Building directly upon the foundational concepts established in Lecture 5 (Maximum Sum of Non-Adjacent Elements / House Robber 1), House Robber 2 introduces a subtle yet critical spatial constraint: circular arrangement.

• The Scenario: Mr. X is a professional robber planning to rob houses along a street. Each house contains a specific, non-negative amount of money.
• The Security Constraint: Adjacent houses have interconnected security systems that automatically alert the police if two neighboring houses are broken into on the same night.
• The Twist: Unlike a standard linear street, the houses here are arranged in a circle. This means the first house is directly adjacent to the last house.

Our objective is to return the absolute maximum amount of money Mr. X can steal tonight without triggering the alarm.

2. Core Mental Model & The Circular Dilemma

To understand the core challenge, let's look at how the circular topology changes our allowable choices compared to a linear array.

Real-Life Analogy: The Circular Jewelry Block

Imagine a ring of houses around a central park. If you burglarize the house at the very top of the ring (House 0), you cannot touch the house immediately to its right, nor can you touch the house immediately to its left (the final house in the array, House $N-1$).

If houses are arranged sequentially in a circle:

Why Lecture 5's Logic Needs a Wrapper

In Lecture 5, we solved the maximum non-adjacent subsequence sum on a straight linear array. If we blindly apply that same linear logic to a circular array, our algorithm might inadvertently pick both House 0 and House $N-1$.

Because the problem states that House 0 and House $N-1$ are adjacent, picking both would instantly trigger the police alarm. We need a strategy to enforce that the first and last houses are never included together in our loot.

3. The Reduction Strategy: Breaking the Circle into Two Linear Problems

How do we eliminate a circular dependency using tools we already understand?

We can reason about the inclusion of the first and last elements:

1. Fact: Any valid robbing configuration can never include both the first house (nums[0]) and the last house (nums[N-1]) simultaneously.
2. Implication: Therefore, our optimal answer must fall into one of two mutually exclusive scenarios:
   • Scenario A: The optimal solution includes the first house, which automatically means it cannot include the last house.
   • Scenario B: The optimal solution includes the last house (or simply considers the array without the first house), meaning it excludes the first house.

Instead of inventing a complex new circular algorithm, we can break the circular array into two separate linear arrays:

Once we split the problem into these two independent linear subsets, we can reuse our exact space-optimized Lecture 5 logic on both arrays and take the maximum of the two results!

4. Edge Cases to Handle Early

Before jumping into code, we must consider structural edge cases that could cause out-of-bounds errors or incorrect logic:

• Single House ($N = 1$): If the array has only one house, there is no adjacency conflict. We simply return that single house's value immediately.
• Two Houses ($N = 2$): If there are two houses, they are both adjacent to each other in a circle. Our reduction correctly handles this because Case 1 evaluates index 0 alone, and Case 2 evaluates index 1 alone, returning the maximum of the two.

5. Step-by-Step Code Implementation

Below is the complete C++ solution demonstrating how we encapsulate the Lecture 5 space-optimized helper function and orchestrate the two-sub-array reduction.

class Solution {
private:
    // Lecture 5 Space-Optimized Logic for Linear House Robber
    long long solveLinear(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        long long prev = nums[0];
        long long prev2 = 0;
        
        for (int i = 1; i < n; i++) {
            long long take = nums[i];
            if (i > 1) {
                take += prev2;
            }
            long long notTake = 0 + prev;
            long long curr = max(take, notTake);
            
            prev2 = prev;
            prev = curr;
        }
        return prev;
    }

public:
    long long rob(vector<int>& nums) {
        int n = nums.size();
        
        // Edge Case: If there is only 1 house, return its value
        if (n == 1) return nums[0];
        
        vector<int> temp1, temp2;
        
        // Populate temp1: Exclude the last element (index n - 1)
        for (int i = 0; i < n - 1; i++) {
            temp1.push_back(nums[i]);
        }
        
        // Populate temp2: Exclude the first element (index 0)
        for (int i = 1; i < n; i++) {
            temp2.push_back(nums[i]);
        }
        
        // Return the maximum of robbing either sub-array
        return max(solveLinear(temp1), solveLinear(temp2));
    }
};

6. Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$
  • We iterate through the array of size $N$ twice (once for temp1 of size $N-1$, and once for temp2 of size $N-1$).
  • Running solveLinear takes linear time $\mathcal{O}(N)$, making the overall time complexity strictly linear.
• Space Complexity: $\mathcal{O}(N)$
  • We create two temporary vectors (temp1 and temp2) to store the sub-arrays, each taking $\mathcal{O}(N)$ auxiliary space.
  • Note: Space can be optimized further to $\mathcal{O}(1)$ auxiliary space if we pass start and end pointers/indices directly into solveLinear without allocating temporary vectors, but creating sub-arrays keeps the code modular and clean.

7. Summary and Key Takeaways

• Circular Constraint Identification: When elements wrap around (first and second/last are neighbors), standard linear DP approaches will violate boundary conditions by picking both ends.
• Problem Reduction Principle: Complex circular problems can often be broken down into two or more simpler linear sub-problems by fixing choices at the boundaries.
• Mutually Exclusive Scenarios: For House Robber 2, the optimal loot either excludes the last house (0 to N-2) or excludes the first house (1 to N-1).
• Leveraging Past Solutions: Never rewrite core logic from scratch if a previous lecture provides a validated building block (solveLinear).
• Modular Design: Encapsulating core algorithms (solveLinear) allows you to reuse code cleanly across transformed problem inputs.
• Edge Case Awareness: Always handle single-element arrays explicitly to avoid runtime faults or incorrect sub-array indexing.