LC 198 & LC 213 & LC 337

Solution to LeetCode 198 House Robber & LeetCode 213 House Robber II & LeetCode 337 House Robber III.

LeetCode 198

House Robber (Medium). [link]

1] Recursion with memorization. (TLE without memorization) For a given house i, we have two options: 1) take the money if we do not robber house i-1. 2) skip it. So the function is rob(n) = max(rob(n-2) + money[i], rob(n-1)). The time complexity is O(n), space complexity is O(n).

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        memo = {}
        def Recursion(nums, i):
            if i < 0: return 0
            if i in memo: return memo[i]
            memo[i] = max(Recursion(nums, i-2) + nums[i], Recursion(nums, i-1))
            return memo[i]
        
        return Recursion(nums, len(nums)-1)

2] Dynamic Programming.

We can consider recursion as a top-down algorithm, and dynamic programming as a bottom-up algorithm.

Let’s define dp[i] as the max amount of money you can rob if there are i houses. The value of dp[i] depends on whether you rob the ith house or not. If you rob the ith house, then dp[i] = dp[i-2]+nums[i]. If you don’t rob the ith house, then dp[i] = dp[i-1]. Therefore, the recurrence relation is dp[i] = max(dp[i-2] + nums[i], dp[i-1]).

The base case is dp[0] = nums[0] if there is one house. dp[1] = max(nums[0],nums[1]) if there are two houses. The result is stored in dp[len(nums)-1].

The time complexity is O(n), space complexity is O(n).

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

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

3] Dynamic Programming with rolling array. Rolling array reduces the space complexity to O(1). The time complexity is O(n), space complexity is O(1).

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cur, pre = 0, 0
        for n in nums:
            cur, pre = max(pre + n, cur), cur
        return cur

LeetCode 213

House Robber II (Medium). [link]

1] DP with Memoization (space optimized)

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def dp(nums):
            cur, pre = 0, 0
            for num in nums:
                cur, pre = max(pre + num, cur), cur
            return cur
        return max(dp(nums[:-1]),dp(nums[1:])) if len(nums) != 1 else nums[0]

2] Top-down DP recursion (TLE)

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
                n = len(nums)
        if n == 1: return nums[0]
        def dp(i, j):
            if j < i: return 0
            return max(nums[j] + dp(i, j-2), dp(i, j-1))
        return max(dp(0,n-2), dp(1,n-1))

3] Bottom-up DP with memoization

Let’s define dp[i] as the max amount of money you can rob if there are i houses. Similar to LC 198, but we have to consider three scenarios:

a] Suppose you do not rob the first and the last houses.

b] Suppose you do not rob the first house (you can rob the last one).

c] Suppose you do not rob the last house (you can rob the first one).

Write in separate functions (easier to understand):

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        # do not rob the first house
        val1 = self.robRange(nums[1:])
        # do not rob the last house
        val2 = self.robRange(nums[:-1])
        return max(val1, val2)
    
    def robRange(self, numlist):
        dp = [0] * len(numlist)
        dp[0] = numlist[0]
        for i in range(1, len(numlist)):
            if i == 1:
                dp[1] = max(numlist[0],numlist[1])
            else:
                dp[i] = max(dp[i-2]+numlist[i], dp[i-1])
        return dp[-1]

All in one function, with two dp arrays (harder to understand):

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 1: 
            return nums[0]
        dp1 = [0] * n
        dp2 = [0] * n
        dp1[1] = nums[1]
        dp2[1] = nums[0]
        
        for i in range(2, n):
            dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i])
            dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i-1])
        return max(dp1[-1], dp2[-1])

LeetCode 337

House Robber III (Medium) [link]

Rather than iterating through a list, we recurse on a tree structure now. Because it is a recursion process, the order is from the leaves to the root.

Let’s define an array of size 2 for each node in the tree {val1, val2}, as the max amount of money if you rob the current node (val1) and if you don’t rob the current node (val2).

If you rob the current node, you don’t rob the children houses. If you do not rob the current node, you can decide rob or not rob the children houses

Dynamic Programming:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        res = self.robTree(root)
        return max(res[0], res[1])

    def robTree(self, node):
        if node is None:
            return (0,0)
        left = self.robTree(node.left)
        right = self.robTree(node.right)
        # rob the current, do not rob the children
        val1 = node.val + left[1] + right[1]
        # do not rob the current, choose to rob or not rob the children
        val2 = max(left[0],left[1]) + max(right[0],right[1])
        return (val1, val2) # rob, not rob