House Robbery

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

Again, the trick to this question is to actually think how to get the maximum house value at a point. For example if we have these houses:

			  0 1 2
houses       [5,1,4]
maxValues    [5,5,_]

For the first two house it's easy, if the question just give us [5,1] we know that we need to rob house 0 for maximum profit

However at 2 we now have 2 choices.

1. Rob house 2 — max_value = max_value(house[0]) + currentHouse
2. Don't rob house 2 — max_value = max_value(house[1])

So basically at house i we have
$$ \text{maxValue}(i) = \max(\text{maxValue[i - 2] + house[i]}, \text{maxValue[i - 1]}) $$

Implementation

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums: return 0
        if len(nums) < 2: return nums[0]

        houseValues = [0] * len(nums)
        
        houseValues[0] = nums[0]
        houseValues[1] = max(nums[0], nums[1])

        for i in range(2, len(nums)):
            houseValues[i] = max(houseValues[i - 2] + nums[i], houseValues[i - 1])
        
        return houseValues[-1]

Time complexity: $O(n)$
Space complexity: $O(n)$

Optimisation

Again, we can improve this further as we only use 2 values:

• houseValues[i]
• houseValues[i - 1]

We can optimise using 2 variables instead

def rob(self, nums: List[int]) -> int:
	if not nums: return 0
	if len(nums) < 2: return nums[0]

	previousHouse = nums[0]
	currentHouse = max(nums[1], previousHouse)

	for i in range(2, len(nums)):
		tmp = currentHouse
		currentHouse = max(nums[i] + previousHouse, currentHouse)
		previousHouse = tmp
	
	return currentHouse

Time complexity: $O(n)$
Space complexity: $O(1)$