House Robber II

Patrick Leaton
Published: May 15, 2021, 7:09 p.m.
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.

 

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 = [0]
Output: 0

 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

 

The description was taken from https://leetcode.com/problems/house-robber-ii/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def rob(self, nums: List[int]) -> int:
        if nums == []:
            return 0
        elif len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums[0], nums[1])
       
        def boogie(start:int, last:int) -> int:
            first, second = nums[start], max(nums[start], nums[start + 1])
            for i in range(start + 2, last):
                third = nums[i]
                first, second = second, max(second, first + third)
            return second
       
        without_last = boogie(0, len(nums)-1)
        without_first = boogie(1, len(nums))
        return max(without_last, without_first)

Problem Explanation

The solution to this question is nearly the same as the first House Robber question, the only difference is we will be making two passes.  

We can solve this problem by walking down the row of houses, looking at three houses at a time, and greedily deciding whether we should rob the edge houses or the middle house.

If the input list is empty, we will return zero because we can't rob any houses.

        if nums == []:
            return 0

 

If the length of the input array is one, we will just rob that single house.

        elif len(nums) == 1:
            return nums[0]

 

If the length of the input array is two, we will just rob whichever of the two houses contains the most money.

        elif len(nums) == 2:
            return max(nums[0], nums[1])

 

Okay, so let's look at what our robbing spree would look like. 

Let's take the test case [1,3,4,2,5,6], for example.  The position of the houses would look more or less like this.

1   3   4  
6   5   2  

 

The numbers in yellow will be visited in both passes.  The number in red will only be visited in the first pass and the number in green will only be visited in the last pass.

With that being said, let's create our function where we can define the bounds of the robbing spree.  It will take a house to start at, a house to finish at, and will return the highest possible loot of the spree, given the requirements.

        def boogie(start:int, last:int) -> int:

 

Now let's start walking down the sidewalk.  

We will start looking at the first two houses, the first house we will consider robbing will be the given start house.  

The second house we will consider robbing will be the greater of the given start house, and the house right next to it, depending on the money inside.

            first, second = nums[start], max(nums[start], nums[start + 1])

 

We will now start our robbing spree by looking at three houses at a time starting from the third house, which is two houses down from the given start house.  We will rob up to the given last house, exclusive.

            for i in range(start + 2, last):

 

The third house will be the house we are standing at during our iteration.

                third = nums[i]

 

To get the best loot, we will need to make a choice each time we take a step down the sidewalk.

Do we rob the middle, second house or do we rob the edge, first and third houses?

                first, second = second, max(second, first + third)

 

Once we have finished a robbing spree and have stuffed our bag of money, we will return the last house we robbed, as that will be the greatest, running max value.

            return second

Now that we have our game plan, let's boogie! 

We will make one pass disregarding the last house, one pass disregarding the first house and we will return which pass gave us the best cash.

        without_last = boogie(0, len(nums)-1)
        without_first = boogie(1, len(nums))
        return max(without_last, without_first)