Solution For House Robber Ii

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.

Step by Step Implementation For House Robber Ii

public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        int res = dp[n - 2];
        dp[1] = nums[1];
        dp[2] = Math.max(nums[1], nums[2]);
        for (int i = 3; i < n; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return Math.max(res, dp[n - 1]);
    }

class Solution:
    def rob(self, nums: List[int]) -> int:
        # edge case
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        # dp array to store max possible value at each index
        dp = [0] * len(nums)
        
        # first pass - consider robbing first house
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, len(nums) - 1):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        
        # second pass - consider not robbing first house
        dp2 = [0] * len(nums)
        dp2[1] = nums[1]
        
        for i in range(2, len(nums)):
            dp2[i] = max(dp2[i-1], dp2[i-2] + nums[i])
        
        # return max of the two passes
        return max(dp[-1], dp2[-1])

//Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 1) return nums[0];
    
    return Math.max(robber(nums, 0, nums.length - 2), robber(nums, 1, nums.length - 1));
};

var robber = function(nums, start, end) {
    let prevNo = 0, prevYes = 0;
    
    for (let i = start; i <= end; i++) {
        let temp = prevNo;
        prevNo = Math.max(prevNo, prevYes);
        prevYes = nums[i] + temp;
    }
    
    return Math.max(prevNo, prevYes);
};

class Solution {
public:
    int rob(vector& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int n = nums.size();
        // dp[i][0] represents the maximum amount of money that can be robbed
        // from houses [0, i) when the robber is not allowed to rob the house at i-1
        // dp[i][1] represents the maximum amount of money that can be robbed
        // from houses [0, i) when the robber is allowed to rob the house at i-1
        vector> dp(n, vector(2, 0));
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        // return the maximum of dp[n-1][0] and dp[n-1][1]
        // since we need to consider the case when the robber is not allowed to rob the house at n-1
        return max(dp[n-1][0], dp[n-1][1]);
    }
};

public class Solution {
    public int Rob(int[] nums) {
        if (nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];
        return Math.Max(RobHelper(nums, 0, nums.Length - 2), RobHelper(nums, 1, nums.Length - 1));
    }
    
    public int RobHelper(int[] nums, int start, int end) {
        int prevNo = 0;
        int prevYes = 0;
        for (int i = start; i <= end; i++) {
            int temp = prevNo;
            prevNo = Math.Max(prevNo, prevYes);
            prevYes = nums[i] + temp;
        }
        return Math.Max(prevNo, prevYes);
    }
}