Welcome to Subscribe On Youtube

3840. House Robber V

Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed and is protected by a security system with a color code.

You are given two integer arrays nums and colors, both of length n, where nums[i] is the amount of money in the ith house and colors[i] is the color code of that house.

You cannot rob two adjacent houses if they share the same color code.

Return the maximum amount of money you can rob.

 

Example 1:

Input: nums = [1,4,3,5], colors = [1,1,2,2]

Output: 9

Explanation:

  • Choose houses i = 1 with nums[1] = 4 and i = 3 with nums[3] = 5 because they are non-adjacent.
  • Thus, the total amount robbed is 4 + 5 = 9.

Example 2:

Input: nums = [3,1,2,4], colors = [2,3,2,2]

Output: 8

Explanation:

  • Choose houses i = 0 with nums[0] = 3, i = 1 with nums[1] = 1, and i = 3 with nums[3] = 4.
  • This selection is valid because houses i = 0 and i = 1 have different colors, and house i = 3 is non-adjacent to i = 1.
  • Thus, the total amount robbed is 3 + 1 + 4 = 8.

Example 3:

Input: nums = [10,1,3,9], colors = [1,1,1,2]

Output: 22

Explanation:

  • Choose houses i = 0 with nums[0] = 10, i = 2 with nums[2] = 3, and i = 3 with nums[3] = 9.
  • This selection is valid because houses i = 0 and i = 2 are non-adjacent, and houses i = 2 and i = 3 have different colors.
  • Thus, the total amount robbed is 10 + 3 + 9 = 22.

 

Constraints:

  • 1 <= n == nums.length == colors.length <= 105
  • 1 <= nums[i], colors[i] <= 105

Solutions

Solution 1: Dynamic Programming

We define two variables $f$ and $g$, where $f$ represents the maximum amount when the current house is not robbed, and $g$ represents the maximum amount when the current house is robbed. Initially, $f = 0$ and $g = nums[0]$. The answer is $\max(f, g)$.

Next, we traverse starting from the second house:

  • If the current house has the same color as the previous house, then $f$ is updated to $\max(f, g)$, and $g$ is updated to $f + nums[i]$.
  • If the current house has a different color from the previous house, then $f$ is updated to $\max(f, g)$, and $g$ is updated to $\max(f, g) + nums[i]$.

Finally, return $\max(f, g)$.

The time complexity is $O(n)$, where $n$ is the number of houses. The space complexity is $O(1)$.

  • class Solution {
    public long rob(int[] nums, int[] colors) {
        int n = nums.length;
        long f = 0, g = nums[0];
        for (int i = 1; i < n; i++) {
            if (colors[i - 1] == colors[i]) {
                long gg = f + nums[i];
                f = Math.max(f, g);
                g = gg;
            } else {
                long gg = Math.max(f, g) + nums[i];
                f = Math.max(f, g);
                g = gg;
            }
        }
        return Math.max(f, g);
    }
}


  • class Solution {
public:
    long long rob(vector<int>& nums, vector<int>& colors) {
        int n = nums.size();
        long long f = 0, g = nums[0];
        for (int i = 1; i < n; i++) {
            if (colors[i - 1] == colors[i]) {
                long long gg = f + nums[i];
                f = max(f, g);
                g = gg;
            } else {
                long long gg = max(f, g) + nums[i];
                f = max(f, g);
                g = gg;
            }
        }
        return max(f, g);
    }
};


  • class Solution:
    def rob(self, nums: List[int], colors: List[int]) -> int:
        n = len(nums)
        f, g = 0, nums[0]
        for i in range(1, n):
            if colors[i - 1] == colors[i]:
                f, g = max(f, g), f + nums[i]
            else:
                f, g = max(f, g), max(f, g) + nums[i]
        return max(f, g)


  • func rob(nums []int, colors []int) int64 {
	n := len(nums)
	var f int64 = 0
	var g int64 = int64(nums[0])

	for i := 1; i < n; i++ {
		if colors[i-1] == colors[i] {
			f, g = max(f, g), f+int64(nums[i])
		} else {
			f, g = max(f, g), max(f, g)+int64(nums[i])
		}
	}

	return max(f, g)
}


  • function rob(nums: number[], colors: number[]): number {
    const n = nums.length;
    let f = 0;
    let g = nums[0];

    for (let i = 1; i < n; i++) {
        if (colors[i - 1] === colors[i]) {
            [f, g] = [Math.max(f, g), f + nums[i]];
        } else {
            [f, g] = [Math.max(f, g), Math.max(f, g) + nums[i]];
        }
    }

    return Math.max(f, g);
}


  • impl Solution {
    pub fn rob(nums: Vec<i32>, colors: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut f: i64 = 0;
        let mut g: i64 = nums[0] as i64;

        for i in 1..n {
            if colors[i - 1] == colors[i] {
                let gg = f + nums[i] as i64;
                f = f.max(g);
                g = gg;
            } else {
                let gg = f.max(g) + nums[i] as i64;
                f = f.max(g);
                g = gg;
            }
        }

        f.max(g)
    }
}

All Problems

All Solutions