LeetCode Solution 213 - House Robber II

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money hidden. The only constraint stopping you from robbing adjacent houses is that all houses are arranged in a circle, meaning the first and last house are also adjacent.

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

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

Optimal Approach - Dynamic Programming (Bottom-Up)

The most efficient way to solve this problem is Dynamic Programming (DP) with two separate cases:

Explanation:

1. Since houses are in a circular arrangement, we need to consider two cases:
   • Case 1: Exclude the last house and rob from index 0 to n-2.
   • Case 2: Exclude the first house and rob from index 1 to n-1.
2. Find the maximum money robbed in both cases and return the larger value.
3. Use the House Robber I solution to compute the maximum money for each case.

Helper Function for House Robber I

int robLinear(vector<int>& nums) {
    int prev1 = 0, prev2 = 0;
    for (int num : nums) {
        int temp = max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = temp;
    }
    return prev1;
}

C++ Code (LeetCode-Compatible)

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        
        vector<int> case1(nums.begin(), nums.end() - 1); // Exclude last house
        vector<int> case2(nums.begin() + 1, nums.end()); // Exclude first house
        
        return max(robLinear(case1), robLinear(case2));
    }
    
private:
    int robLinear(vector<int>& nums) {
        int prev1 = 0, prev2 = 0;
        for (int num : nums) {
            int temp = max(prev1, prev2 + num);
            prev2 = prev1;
            prev1 = temp;
        }
        return prev1;
    }
};

Step-by-Step Explanation

1. Edge Case: If there's only one house, return nums[0].
2. Case 1: Compute the max robbing amount by excluding the last house.
3. Case 2: Compute the max robbing amount by excluding the first house.
4. Return the maximum from both cases.

Dry Run / Execution Steps

Example:

Input: nums = [2,3,2]

Two Cases:

1. Excluding the last house → nums = [2,3], Max Robbery = 3
2. Excluding the first house → nums = [3,2], Max Robbery = 3 Output: 3

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Recursion)	Exponential $O(2^n)$	O(n)	Too slow for large inputs
Memoization (Top-Down DP)	O(n)	O(n)	Extra space usage
Bottom-Up DP (Best)	O(n)	O(1)	Optimized for both time and space

Best Solution & Why It’s Best

The Bottom-Up DP approach is the most efficient because:

1. It avoids recursion overhead.
2. It only requires O(1) space, unlike memoization.
3. It guarantees an optimal solution with O(n) time complexity.

Complexity Analysis

• Time Complexity: O(n), iterating through the array twice.
• Space Complexity: O(1), only using two extra variables.

Conclusion

• The best approach is Bottom-Up Dynamic Programming.
• Other methods like recursion or memoization use unnecessary extra space or time.
• Recommended practice problems:
  • House Robber I (LeetCode 198)
  • Paint House (LeetCode 256)
  • Maximum Sum of Non-Adjacent Elements