LeetCode Solution 198 - House Robber

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 you cannot rob two adjacent houses. 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] <= 400

Optimal Approach - Dynamic Programming (Bottom-Up)

The most efficient way to solve this problem is Dynamic Programming (DP).

Explanation:

1. Maintain a dp array where dp[i] represents the maximum money that can be robbed up to house i.
2. Transition Formula:
   • dp[i] = max(dp[i-1], nums[i] + dp[i-2])
   • Either rob the current house and add it to dp[i-2] or skip the house and take dp[i-1].
3. Use two variables to store the last two results instead of an entire array for space optimization.

C++ Code (LeetCode-Compatible)

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        
        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. Base Cases:
   • If nums is empty, return 0.
   • If nums has only one element, return nums[0].
2. Iterate Over Houses:
   • At each house, calculate whether to rob it (prev2 + nums[i]) or skip it (prev1).
   • Update prev1 and prev2 accordingly.
3. Return the Maximum Stolen Value.

Dry Run / Execution Steps

Example:

Input: nums = [2,7,9,3,1]

DP Calculation:

House 1: Rob -> 2
House 2: Rob -> max(2, 7) = 7
House 3: Rob -> max(7, 2 + 9) = 11
House 4: Rob -> max(11, 7 + 3) = 11
House 5: Rob -> max(11, 11 + 1) = 12

Output: 12

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 once).
• Space Complexity: O(1) (using only two variables instead of an array).

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 II (LeetCode 213)
  • Paint House (LeetCode 256)
  • Maximum Sum of Non-Adjacent Elements