Crack the house robber problem

My previous post introduced the Knapsack problem. It states how to solve using the dynamic programming algorithm. Besides Knapsack, there’s one series of problems that you might encounter in a coding interview: the house robber problems. Today, let’s talk about it.

Problem description

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Examples:

Case 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.
Case 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.

From the description and examples, we know the robber has to find out the maximum profit for the given houses without stealing two adjacent houses. How to solve it?

Solution

It seems complicated at the first glance. In fact, if we break it into subproblems, there are only two scenarios to consider: at the current house, will the robber rob it? There are two cases to consider:

• At house i, if the robber robs it, meaning that the robber didn’t rob the previous house i-1, the maximum profit could be profit at the house i-2 plus current house valuei
• At house i, if the robber doesn’t rob it, meaning that the previous house i-1 could be robbed, the maximum profit might happen at the house i-1

As the result, at house i, the maximum profit is determined by its previous houses: profit[i] = max(profit[i-2]+house[i], profit[i-1]) . To compare these two values, the best way is to create an array to store the profit.

Let’s take one example to walk through the process:

Input: nums = [2,7,9,3,1]
Step 1: 
Let's create an array to store the maximum proit the robber robbed. Let's set initial profits all to 0: profit = [0,0,0,0,0,0]. Note that we increate the profit size by 1, it means when i = 0, the profit is zero due to the None house value. 
Step 2:
Initial state is that when i = 0, profit[0] = 0. When i = 1, profit[1] = nums[0] = 2 because it's the maximum profit if we only go over one house. Now profit = [0,2,0,0,0,0]
Step 3:
Start with index = 2, let's find the maximum profit while iterating the houses.
When i = 2, current house value is 7, consider two cases here:
    * rob it: profit[2] = profit[2-2] + 7 = 7
    * not rob it: profit[2] = profit[2-1] = 2 
Obviously, 7 is bigger, profit = [0,2,7,0,0,0]
Step 4:
Move to index = 3, current house value is 9, consider two cases here:
    * rob it: profit[3] = profit[3-2] + 9 = 11
    * not rob it: profit[3] = profit[3-1] = 7
Obviously, 11 is bigger, profit = [0,2,7,11,0,0]
Step 5:
Move to index = 4, current house value is 3, consider two cases here:
    * rob it: profit[4] = profit[4-2] + 3= 10
    * not rob it: profit[4] = profit[4-1] = 11
Obviously, 11 is bigger, profit = [0,2,7,11,11,0]
Step 5:
Move to the last house index = 5, current house value is 1, consider two cases here:
    * rob it: profit[5] = profit[5-2] + 1 = 12
    * not rob it: profit[5] = profit[5-1] = 11
Obviously, 12 is bigger, profit = [0,2,7,11,11,12]
Step 6:
Now, we've seen all given houses: profit = [0,2,7,11,11,12]. The maximum profit is 12. 

Code:

    def rob(nums):
        if not nums or len(nums) == 0:
            return 0
        
        res = nums[0]
        profit = [0] * (len(nums) + 1)
        profit[1] = nums[0]
        
        
        for i in range(2, len(profit)):
            profit[i] = max(nums[i-1] + profit[i-2], profit[i-1])
            res = max(res, profit[i])
  
        return res

Analysis:

Let n be the number of the given houses:

• Time complexity: O(n) since we iterate the nums once, and saved the result at an array.
• Space complexity: O(n) since we create an extra array with size n+1 to help to find the maximum profit.

House Robber II

There’s a more challenging version of the house robber problem:

Description:

You 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 a list of non-negative integers nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Examples:

Case 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.
Case 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.

Solution

When the houses are circular, it’s different from the previous problem because the first house and last house can’t be robbed at the same time. How to solve it?

In fact, we can divide it into two subproblems:

• Don’t rob the first house, what’s the maximum profit robbed?
• Don’t rob the last house, what’s the maximum profit robbed?

Each subproblem could be solved using the previous algorithm. The only part that needs to change is that for the don’t rob front case: profit[1] = 0. To record the maximum profit of two different cases, we’ll create two different arrays: notRobFront, and notRobTail . After iterating the houses, we’ll compare two arrays to find the maximum profit.

Code:

    def rob(nums):
        size = len(nums)
        notRobFront = [0] * (size + 1)
        notRobTail = [0] * (size + 1)
        notRobFront[1] = 0
        notRobTail[1] = nums[0]
        for i in range(2, size):
            notRobFront[i] = max(notRobFront[i-1], notRobFront[i-2]+nums[i-1])
            notRobTail[i] = max(notRobTail[i-1], notRobTail[i-2]+nums[i-1])
        notRobFront[-1] = max(notRobFront[size-1], notRobFront[size-2] + nums[-1])
        return max(notRobFront[-1], notRobTail[-2])

Analysis:

Let n be the number of the given houses:

• Time complexity: O(n) since we iterate the nums once, and saved the result at an array.
• Space complexity: O(2n) ≈ O(n) since we create two extra arrays with size n+1 to help to find the maximum profit.

Thanks for reading!

Reference

House Robber - LeetCode

House Robber II - LeetCode