House Robber II problem - Leetcode 213

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

Question

YYou are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system 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 = [2,3,2]
• Output: 3
• Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

• 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 3:

• Input: nums = [1,2,3]
• Output: 3

Intuition

This problem is an expansion of the Problem #198 - House Robber where they add an addition restriction that all houses form a circle (i.e., the last house is a neighbor the first house). Thus we can just adapt the code of the Problem #198 for this problem.

Approach

There are also two approaches same as the problem #198:

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

Brute-force Approach

In the problem #198, the brute-force approach as below:

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.

Now the approach is extended to exclude the binary vector where the first and the last element are 1s to take into account for the additional restriction. Thus, I just added an additional code:

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
    +for i, lst in enumerate(result):
    +   if len(lst) > 1:
    +       if lst[0] * lst[-1] != 0:
    +           result.pop(i)
    return result

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.