House Robber Ii - Leetcode Solution

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 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 nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Solution: This problem is a follow-up of the House Robber I problem. The difference is that in this problem, the houses are arranged in a circle. This means that if we rob the first house, we cannot rob the last house, and if we rob the last house, we cannot rob the first house.

To find the maximum amount of money we can rob, we can use a Dynamic Programming approach. We can create two arrays, dp1 and dp2, where dp1[i] represents the maximum amount of money we can rob from the i-th house without robbing the first house, and dp2[i] represents the maximum amount of money we can rob from the i-th house without robbing the last house.

To fill these two arrays, we can use the same recurrence relation as in the House Robber I problem. For dp1, we have dp1[i] = max(dp1[i-2] + nums[i], dp1[i-1]), and for dp2, we have dp2[i] = max(dp2[i-2] + nums[i], dp2[i-1]), where i represents the i-th house.

After filling these two arrays, we can find the maximum amount of money we can rob by taking the maximum of dp1[n-2] and dp2[n-1], where n is the length of the nums array.

The reason we take dp1[n-2] instead of dp1[n-1] is that we cannot rob the first house, and the i-th house corresponds to the i-1 index in the dp array. Similarly, we take dp2[n-1] instead of dp2[n-2] because we cannot rob the last house.

Here is the Python implementation of the solution:

def rob(nums): # base cases if len(nums) == 0: return 0 if len(nums) == 1: return nums[0] if len(nums) == 2: return max(nums)

# fill dp1 array
dp1 = [nums[0], max(nums[0], nums[1])]
for i in range(2, len(nums)-1):
    dp1.append(max(dp1[i-2] + nums[i], dp1[i-1]))

# fill dp2 array
dp2 = [0, nums[1]]
for i in range(2, len(nums)):
    dp2.append(max(dp2[i-2] + nums[i], dp2[i-1]))

# return the maximum amount of money we can rob
return max(dp1[-1], dp2[-1]) 

Time complexity: O(n) Space complexity: O(n)

This solution has a time complexity of O(n) and a space complexity of O(n), where n is the length of the nums array.

1