Blind 75 - problem 17 : House Robber II

 

House Robber II - LeetCode Solution & Explanation

Problem Statement

The House Robber II problem is an extension of the House Robber problem with an additional constraint:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. However, all houses are arranged in a circle, meaning the first and last houses are adjacent.

You cannot rob both the first and last houses. Determine the maximum amount of money you can rob without robbing two adjacent houses.

Constraints

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

Example 1

Input: nums = [2,3,2]
Output: 3
Explanation: Rob house 2 (3), total = 3.

Example 2

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 2 (2) and house 4 (1), total = 2 + 1 = 4.

Example 3

Input: nums = [1,2,3]
Output: 3
Explanation: Rob house 2 (3), total = 3.

---

Optimal Approach: Dynamic Programming (DP)

Since the houses are arranged in a circle, we cannot rob both the first and last house.
To solve this, we split the problem into two cases:

1. Case 1: Consider houses from index [0, n-2] (excluding the last house).
2. Case 2: Consider houses from index [1, n-1] (excluding the first house).

Then, we apply the House Robber I solution to both cases and return the maximum loot from either case.

Mathematically:

$$\text{result} = \max(\text{rob}(nums[0:n-1]), \text{rob}(nums[1:n]))$$

where rob() is the standard House Robber I function.

---

LeetCode-Compatible C++ Solution

class Solution {
public:
    int robRange(vector<int>& nums, int start, int end) {
        int prev1 = 0, prev2 = 0;
        for (int i = start; i <= end; i++) {
            int temp = prev1;
            prev1 = max(prev1, prev2 + nums[i]);
            prev2 = temp;
        }
        return prev1;
    }
    
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        return max(robRange(nums, 0, nums.size() - 2), robRange(nums, 1, nums.size() - 1));
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

---

Step-by-Step Explanation

1. Edge Case: If there is only one house, return its value directly.
2. Define robRange(nums, start, end):
   • Uses Dynamic Programming (DP)
   • Maintains prev1 (max loot up to i-1) and prev2 (max loot up to i-2).
   • Iterates from start to end, updating prev1 and prev2 dynamically.
3. Compute the maximum loot:
   • Call robRange(nums, 0, n-2) → Robbing from first to second-last house.
   • Call robRange(nums, 1, n-1) → Robbing from second to last house.
   • Return the maximum of both cases.

---

Dry Run (Execution Steps)

Let's take nums = [2,3,2]:

Case 1: Robbing from index 0 to n-2 → [2,3]

Step	Current House Value	prev1 (max so far)	prev2 (before prev1)
Init	-	0	0
1st	2	2	0
2nd	3	3	2

Output for Case 1: 3

---

Case 2: Robbing from index 1 to n-1 → [3,2]

Step	Current House Value	prev1 (max so far)	prev2 (before prev1)
Init	-	0	0
1st	3	3	0
2nd	2	3	3

Output for Case 2: 3

---

Final Output:

$$\max(3, 3) = 3$$

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force Recursion	O(2^n)	O(n)	Exponential time, too slow for n=100
Memoization (Top-Down DP)	O(n)	O(n)	Extra recursion stack overhead
Bottom-Up DP (Array Storage)	O(n)	O(n)	Requires O(n) extra space
Optimized DP (Two Variables)	O(n)	O(1)	Best trade-off between time and space

---

Best Solution & Why?

The Optimized DP with two variables is the best choice because:
✅ Linear Time Complexity (O(n)) – Efficient for large n.
✅ Constant Space Complexity (O(1)) – No extra DP array needed.
✅ Simple Code – Easy to implement with only two variables.

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute Force Recursion	O(2^n)	O(n)
Memoization (Top-Down DP)	O(n)	O(n)
Bottom-Up DP (Array)	O(n)	O(n)
Optimized DP (Two Variables)	O(n)	O(1)

---

Conclusion

• Best Approach: Optimized DP using O(n) time and O(1) space.
• Why? Avoids recursion and unnecessary memory allocation.
• Similar Problems to Practice:
  1. House Robber LeetCode #198
  2. Paint House LeetCode #256
  3. Delete and Earn LeetCode #740