House Robber II

LeetCode

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

Initial attempt

Time spent: 39m | Runtime: 70.94% | Memory: 20.03%

• I spent a lot of time trying to solve the problem at each subproblem. This meant keeping a lot of state. While this somewhat worked, it was pretty complicated.

Solution

• As the problem title suggests, knowing House Robber is a huge boost. The recurrence relationship here is the same as in that problem.
• The "trick" is to recognize that the problem boils down the following.

house_robber_ii_answer = max(
    house_robber_without_first_element,
    house_robber_without_last_element,
)

The intuition here is to notice the solution to House Robber will have exactly one of the following qualities.

1. First and last elements are included.
2. First element is included, last element is excluded.
3. First element is excluded, last element is included.
4. First and last elements are excluded.

For this problem, we're disallowing (1) from being our solution. By forcing either first or last to be missing, we can find our answer.

Note that this "problem solving" portion is not dynamic programming. Just a "gotcha" that can ruin your day if you don't "get it".

Cleaned up code

Time spent: 9m | Runtime: 22.41% | Memory: 94.13%

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

        no_first_prev = 0
        no_first_current = 0
        for i, num in enumerate(nums):
            if i != len(nums) - 1:
                first_prev, first_current = (
                    first_current,
                    max(first_current, first_prev + num),
                )
            if i != 0:
                no_first_prev, no_first_current = (
                    no_first_current,
                    max(no_first_current, no_first_prev + num),
                )

        if len(nums) == 1:
            return nums[0]
        else:
            return max(first_current, no_first_current)