LeetCode Solutions Blog

House Robber

Number: 198

Difficulty: Medium

Paid? No

Problem Description

Given an integer array representing the amount of money at each house, determine the maximum amount you can rob without triggering the security system, which is activated if two adjacent houses are robbed.

Key Insights

The problem can be solved using Dynamic Programming.
For each house, decide whether to rob it or not.
Recurrence relation: dp[i] = max(dp[i-1], dp[i-2] + currentHouseMoney)
Use iterative computation to keep track of the optimal solutions without needing extra space for the entire dp array.

Space and Time Complexity

Time Complexity: O(n), where n is the number of houses. Space Complexity: O(1), using only two variables to track the previous decisions.

Solution

We use a dynamic programming approach by iterating through each house in the array. At each step, we consider two scenarios: either we rob the current house (and add its money to the total from two houses ago) or we skip it (keeping the optimal solution up to the previous house). By using two variables to store these intermediate results, we achieve an optimized space complexity of O(1).

Code Solutions

# Definition of the Solution class
class Solution:
    def rob(self, nums: List[int]) -> int:
        # Edge case: if there are no houses, return 0
        if not nums:
            return 0
        
        # Initialize two variables to keep track of the max amounts
        prev1, prev2 = 0, 0
        
        # Iterate over each house's money
        for money in nums:
            # Calculate the maximum money that can be robbed if we consider the current house
            current = max(prev1, prev2 + money)  # Either skip current house or rob it
            # Update variables: prev2 becomes previous best, and prev1 becomes current best
            prev2 = prev1
            prev1 = current
        
        # Return the maximum money that can be robbed
        return prev1