House Robber

Patrick Leaton
Published: March 28, 2021, 9:44 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, 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.

 

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.

 

Constraints:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

 

Description taken from https://leetcode.com/problems/house-robber/.

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])
        first, second = nums[0], max(nums[0], nums[1])
        for i in range(2, len(nums)):
            third = nums[i]
            first, second = second, max(second, first + third)       
        return second

 

Problem Explanation

This problem is a variation of Climbing Stairs, but there is a new addition of a greedy component.

That problem and the running combination Dynamic Programming problems like it, utilize a pattern of arriving at a point B and tabulating the combinations of each point A it could have gotten therefrom.

This problem requires making choices to gain the biggest running sum. 

We can solve this problem by walking down the row of houses and looking at three houses at a time.  Each time we do this, we will make a greedy decision to either rob the middle house or rob the first and third houses, based on the maximum loot value.   Once we make that calculation, that will be where we will begin the next iteration from.

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])

 

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 first house in the input array.  

The second house we will consider robbing will be the greater of the first and second houses in the input array, depending on money.

        first, second = nums[0], max(nums[0], nums[1])

 

We will now start our robbing spree by looking at three houses at a time starting from the third house, index two.

        for i in range(2, len(nums)):

 

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 our 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