LeetCode #213: House Robber II

LeetCode Solutions

https://leetcode.com/problems/house-robber-ii/

The House Robber II problem is similar to the House Robber problem, except that the houses are arranged in a circular manner. This means that the first and the last houses are adjacent, and robbing one of them means that the other cannot be robbed. The goal is to find the maximum amount of money that can be robbed from these houses without robbing any two adjacent houses.

The problem asks us to determine the maximum amount of money that can be robbed from a row of houses, while considering the constraint that no two adjacent houses can be robbed.

Here are the steps to solve this problem using dynamic programming:

  1. Create a helper function that can solve the simpler problem of robbing from a single row of houses without considering the circular constraint. We can use the same dynamic programming approach that we used for the previous House Robber problem.
  2. Check if the input list of houses has only one house. If it does, then we can simply return the value of that house.
  3. Return the maximum of two cases:
    • Rob the first house to the second-to-last house and run our helper function on it.
    • Rob the second house to the last house and run our helper function on it.
  4. Return the maximum value obtained from step 3.

Here’s the implementation of the above approach:

class Solution:
    def rob(self, nums: List[int]) -> int:
        def rob1(nums):
            rob1, rob2 = 0, 0
            for n in nums:
                temp = max(rob1+n, rob2)
                rob1 = rob2
                rob2 = temp
            return rob2
        
        if len(nums) == 1:
            return nums[0]
        
        return max(rob1(nums[1:]), rob1(nums[:-1]))

Time complexity

O(n) where n is the length of the input list of houses.

Space complexity

O(1) as we use only a constant amount of extra space for variables.