House Robber problem - Leetcode 198

A notes on the Problem #198 - House Robber on Leetcode when I practiced Dynamic Programming.

Question

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 each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

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

Example 1:

• Input: nums = [1,2,3,1]
• Output: 4
• Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Example 2:

• Input: nums = [2,7,9,3,1]
• Output: 12
• Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

Intuition

The core intuition behind this problem is:

When standing in front of a house, you have to decide whether to rob it or not. If you choose to rob it, make sure not to trigger the security system by robbing adjacent houses.

Approach

With that in mind, I explored two approaches:

• Brute-force approach
• Dynamic Programming (DP) approach

Brute-force Approach

This approach considers all valid combinations of houses that can be robbed without triggering the alarm system. To do this, I generated all binary lists of length n, where each element is either 0 or 1. A 1 at position i indicates that the i-th house is robbed, and 0 means it’s skipped. To ensure we don’t rob two adjacent houses, we filter out any combinations where two 1s are next to each other.

Here’s the implementation for generating those valid combinations:

1
2
3
4
5
6
7
8
9
10
11
12
 
def generate_binary_lists(n):
    result = [[0], [1]]
    for _ in range(1, n):
        new_result = []
        for lst in result:
            if lst[-1] == 1:
                new_result.append(lst + [0])
            else:
                new_result.append(lst + [1])
                new_result.append(lst + [0])
        result = new_result
    return result
 

Once we have all the valid combinations, we calculate the amount of money we can rob for each and keep track of the maximum:

1
2
3
4
5
6
7
8
9
10
11
 
def rob(nums):
    all_binary_lists = generate_binary_lists(len(nums))
    max_money = float("-inf")
    current_max_robbed_house = None
    for lst in all_binary_lists:
        current_money = 0
        for i in range(len(lst)):
            current_money += lst[i] * nums[i]
            if current_money > max_money:
                max_money = current_money
    return max_money, current_max_robbed_house
 

This approach worked for 47 out of 70 test cases on LeetCode. However, it failed with a Memory Limit Exceeded error on the $48^{th}$ test case due to the exponential number of combinations.

Dynamic Programming Approach

To address the memory issue, I turned to dynamic programming.

Observation

At any house i, you have two choices:

1. Rob house i: You must skip house i-1, so the total is the value at house i plus the max value when house i-1 wasn’t robbed.
2. Skip house i: You take the max of robbing or skipping house i-1.

Step-by-Step Example

Let’s walk through the array [2, 7, 9, 3, 1].

At the end, we return:

max(rob, not_rob) = max(12, 11) = 12

Implementation

We use two variables to keep track of:

• rob_amount: max money if we rob the current house.
• not_rob_amount: max money if we skip the current house.

We update these as we iterate through the houses:

1
2
3
4
5
6
7
8
9
10
11
12
 
def rob(nums):
    rob_amount = 0
    not_rob_amount = 0
    for i in range(len(nums)):
        # if rob this i-th house
        if i == 0:
            rob_amount += nums[i]
        else:
            amount_if_rob = not_rob_amount + nums[i]
            not_rob_amount = max(rob_amount, not_rob_amount)
            rob_amount = amount_if_rob
    return max(not_rob_amount, rob_amount)
 

This solution is efficient and passes all test cases. It runs in O(n) time and uses O(1) space.