House Robber II medium

Problem Statement

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 a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Steps and Explanation

The key insight is that because the houses are arranged in a circle, robbing the first house automatically prevents robbing the last house, and vice versa. Therefore, we can solve this problem by considering two cases:

1. Rob the first house: In this case, we cannot rob the last house. We solve the house robbing problem for the subarray nums[0:len(nums)-1].
2. Don't rob the first house: In this case, we can rob the last house. We solve the house robbing problem for the subarray nums[1:len(nums)].

We then return the maximum of the two results. The subproblem of robbing a linear array of houses can be solved using dynamic programming (similar to House Robber I).

Code

def rob(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]

    def rob_linear(houses):
        n = len(houses)
        if n == 0:
            return 0
        if n == 1:
            return houses[0]
        dp = [0] * n
        dp[0] = houses[0]
        dp[1] = max(houses[0], houses[1])
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + houses[i])
        return dp[n-1]


    # Case 1: Rob the first house, skip the last
    rob1 = rob_linear(nums[:-1])

    #Case 2: Skip the first house, can rob the last
    rob2 = rob_linear(nums[1:])

    return max(rob1, rob2)

Complexity

• Time Complexity: O(n), where n is the number of houses. This is due to the linear time complexity of the rob_linear function, which is called twice.
• Space Complexity: O(n) in the worst case due to the dp array used in rob_linear. This can be optimized to O(1) by only keeping track of the previous two maximum amounts, but the code above prioritizes clarity.