Problem Statement in English

You’re given a list of profits, nums, that you can gain from robbing house[i]. You can’t rob $2$ consecutive houses because that’ll trigger the alarm. Your task is to return the max profit you can gain by robbing houses without getting caught.

Approach

When you think about it, all this problem really needs is for you to find the best run from the past that doesn’t include the previous house.

From there the only thing you can improve is the time complexity of finding that most profitable heist. Using the naive approach of calculating max(all heists excluding the previous house) results in redundant computation and can be optimised.

At every point in time we maintain the $2$ best heist runs, one including the previous house, and one without it (which means it goes until $1$ house before the previous one). However, in case the run excluding the previous house is worse than the one before that, we end up storing the same heist run twice.

For example, to calculate the best heist for house $4$, we use the best run until house $2$ and add the profits from house $4$ to it. If that’s less than the best run till house $3$, then we retain the best run until house $3$ again. This means lookup will contain [run till house 3, run till house 3], and we’ll process house $5$ with that.

If didn’t fully follow, that’s alright, try going through the code and then coming back to this.

Solution in Python


class Solution:
    def rob(self, nums: List[int]) -> int:

        # base cases
        if len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums[0], nums[1])

        # we only store 2 values, so it uses O(1) space and
        # allows constant time lookup for the best possible sum
        lookup = [nums[0], max(nums[0], nums[1])]

        for i in range(2, len(nums)):
            # we can't use this value for the current house
            # because this house is on the immediate left of the one we're processing
            # and robbing consecutive house will trigger the alarm
            temp = lookup[-1]
            # store the most profitable run until the current house
            lookup[-1] = max(lookup[-1], lookup[-2] + nums[i])
            # store the most profitable run until the previous house
            lookup[-2] = temp

        # return the best possible sum
        return max(lookup[-1], lookup[-2])

Complexity

  • Time: $O(n)$
    Since we process $n$ houses at most.

  • Space: $O(1)$
    Since we only store $2$ heist runs.

Mistakes I Made

I made some mistakes with the mechanics of updating lookup.

And we are done.