Skip to content

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

Thinking

Adjacent houses of the same color cannot both be robbed; different colors have no such ban. \(n \le 10^5\) needs a linear DP.

The usual rob/skip transition still holds for equal colors; for different colors the current house may follow a robbed previous house.

Let \(f,g\) be the best skip/rob amounts after the previous house. Same color: \(g\) comes only from old \(f\). Different colors: \(g\) comes from \(\max(f,g)\).

Two rolling variables suffice; the answer is their maximum.

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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)
    }
}

Comments