SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem involves finding the maximum amount of money you can rob from a list of houses arranged in a circular manner. Each house has a certain amount of money, but you cannot rob two adjacent houses. Since the houses are in a circle, the first and last houses are also adjacent, making the problem more complex.

Intuition

The problem is a variation of the classic "House Robber" problem, but with a circular arrangement of houses. The circular nature means that if you rob the first house, you cannot rob the last house and vice versa. This requires solving the problem twice—once ignoring the first house and once ignoring the last house.

Approach

1. Edge Case:

   • If there is only one house, return its value as the result.

2. Divide and Conquer:

   • Divide the problem into two sub-problems:
     • Sub-problem 1: Consider robbing houses from the first house to the second-last house.
     • Sub-problem 2: Consider robbing houses from the second house to the last house.

3. Dynamic Programming:

   • For each sub-problem, apply the dynamic programming approach to find the maximum money that can be robbed.
   • Maintain two variables, prevRob and maxRob, where prevRob keeps track of the maximum amount robbed up to the previous house, and maxRob keeps track of the maximum amount robbed up to the current house.

4. Final Step:

   • Return the maximum value between the results of the two sub-problems.

Complexity

Time Complexity:

O(n), where n is the number of houses. The algorithm iterates through the houses twice (once for each sub-problem), but each iteration is linear.

Space Complexity:

O(1). The algorithm uses a constant amount of extra space to store the variables prevRob and maxRob.

Code

C++

class Solution {
public:
    int rob(vector<int>& nums) {
        auto getMax = [](const vector<int>& nums) {
            int prevRob = 0, maxRob = 0;
            for (int curVal : nums) {
                int temp = max(maxRob, prevRob + curVal);
                prevRob = maxRob;
                maxRob = temp;
            }
            return maxRob;
        };

        if (nums.size() == 1) return nums[0];
        int max1 = getMax(vector<int>(nums.begin(), nums.end() - 1));
        int max2 = getMax(vector<int>(nums.begin() + 1, nums.end()));
        return max(max1, max(max2, nums[0]));
    }
};

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        def getMax(nums):
            prevRob, maxRob = 0, 0
            for curVal in nums:
                temp = max(maxRob, prevRob + curVal)
                prevRob = maxRob
                maxRob = temp
            return maxRob
        
        if len(nums) == 1:
            return nums[0]
        return max(getMax(nums[:-1]), getMax(nums[1:]), nums[0])

Java

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        
        int max1 = getMax(Arrays.copyOfRange(nums, 0, nums.length - 1));
        int max2 = getMax(Arrays.copyOfRange(nums, 1, nums.length));
        return Math.max(max1, max2); // This compares max1 and max2

        // If you want to compare all three (max1, max2, and nums[0]):
        // return Math.max(Math.max(max1, max2), nums[0]);
    }

    private int getMax(int[] nums) {
        int prevRob = 0, maxRob = 0;
        for (int curVal : nums) {
            int temp = Math.max(maxRob, prevRob + curVal);
            prevRob = maxRob;
            maxRob = temp;
        }
        return maxRob;
    }
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var rob = function(nums) {
    const getMax = (nums) => {
        let prevRob = 0, maxRob = 0;

        for (let curVal of nums) {
            let temp = Math.max(maxRob, prevRob + curVal);
            prevRob = maxRob;
            maxRob = temp;
        }

        return maxRob;
    };

    if (nums.length === 1) return nums[0];
    return Math.max(getMax(nums.slice(0, -1)), getMax(nums.slice(1)), nums[0]);    
};