Blind 75 - problem 16 : House Robber

House Robber - LeetCode Solution & Explanation

Problem Statement

The House Robber problem is a Dynamic Programming (DP) question from LeetCode.

Problem:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing them all is that adjacent houses have security systems connected. If two adjacent houses are robbed, the police will be alerted.

Task:
Determine the maximum amount of money you can rob without robbing two adjacent houses.

Constraints

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

Example 1

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

Example 2

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (2), house 3 (9), house 5 (1), total = 2 + 9 + 1 = 12.

---

Optimal Approach: Dynamic Programming (Bottom-Up)

Since we cannot rob adjacent houses, we have two choices at each house i:

1. Skip the house (i), keep previous maximum loot.
2. Rob the house (i), add its value to the maximum loot at house i-2 (since i-1 cannot be robbed).

Mathematically:

$$dp[i] = \max(dp[i-1], nums[i] + dp[i-2])$$

Where:

• dp[i-1] means skipping the current house.
• nums[i] + dp[i-2] means robbing this house and taking the amount robbed two houses before.

Optimized Space Complexity (O(1))

Instead of using an array, we store only the last two results to save space.

---

LeetCode-Compatible C++ Solution

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

Time Complexity: O(n)

Space Complexity: O(1)

---

Step-by-Step Explanation

1. Edge Case: If there’s only one house, return its value directly.
2. Initialize variables: prev1 = 0 (max loot up to i-1), prev2 = 0 (max loot up to i-2).
3. Iterate over houses (nums):
   • Temporarily store prev1 value.
   • Update prev1 = max(prev1, prev2 + nums[i]) (rob or skip the current house).
   • Shift prev2 = temp (update to previous house loot).
4. Return prev1, which holds the maximum possible robbery amount.

---

Dry Run (Execution Steps)

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

Step	Current House Value	prev1 (max so far)	prev2 (before prev1)
Init	-	0	0
1st	2	2	0
2nd	7	7	2
3rd	9	11 (prev2+9)	7
4th	3	11	11
5th	1	12 (prev2+1)	11

Final Output: 12

---

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 II LeetCode #213
  2. Paint House LeetCode #256
  3. Maximum Sum of Non-Adjacent Elements LeetCode Variation