Devin's Blog

House Robber II

3 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Warning

Be careful when caching, since @cache requires that the input array not change in subsequent calls.

Intuition

Top Down

  • Similar to House Robber, you have the choice of robbing a house or not robbing a house.
  • However, since the first and last element are “adjacent to each other”, one could try the following approach in top down:
    • Remove the first element, and recurse, then remove the last element bringing back in the first element, then recurse.
  • That way, it is guaranteed that if one element is picked, the other element is not picked.
  • The following approach does not work:
    • Extend the left and right with the right element on the left and left element on the right.
  • That is because you still have a chance of keeping duplicate elements.

Bottom Up

  • On each iteration, store the previous house’s optimal, along with the maximum if you kept the optimal versus added to the previous previous optimal.

Complexity

Runtime

Space

  • if using the bottom up approach, since we aren’t creating any new arrays.

Code

Bottom Up

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
 
        pp_opt, p_opt = 0, 0
        for i in range(1, n):
            pp_opt, p_opt = p_opt, max(p_opt, nums[i] + pp_opt)
        r1 = p_opt
 
        pp_opt, p_opt = 0, 0
        for i in range(n - 1):
            pp_opt, p_opt = p_opt, max(p_opt, nums[i] + pp_opt)
        
        r2 = p_opt
        return max(r1, r2)

Top Down

Array

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
 
        def r(i):
            if i < 0:
                return 0
            if dp[i] != -1:
                return dp[i]
 
            sr1 = nums[i] + r(i - 2)
            sr2 = r(i - 1)
            dp[i] = max(sr1, sr2)
            return dp[i]
 
        tmp = nums.pop()
        dp = [-1] * len(nums)
        r1 = r(len(nums) - 1)
        nums.append(tmp)
        nums.pop(0)
        dp = [-1] * len(nums)
        r2 = r(len(nums) - 1)
        return max(r1, r2)

Hashmap

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
 
        def r(i):
            if i < 0:
                return 0
            if i in dp:
                return dp[i]
 
            sr1 = nums[i] + r(i - 2)
            sr2 = r(i - 1)
            dp[i] = max(sr1, sr2)
            return dp[i]
 
        tmp = nums.pop()
        dp = {}
        r1 = r(len(nums) - 1)
        nums.append(tmp)
        nums.pop(0)
        dp = {}
        r2 = r(len(nums) - 1)
        return max(r1, r2)

Notes

Cards

START Basic Front: House Robber II Back:

END

References

Graph View