Problem

There was a thief, he has to pass through colored house - which can be red or blue, and contain 0 or more gems. The property of these gems is they multiply the previous gems by the current gems in the house. The houses are in array and thief can only visit once to steal the gems, with the goal of maximizing the gems. Find the range of house where he can maximize the gems in such a way that number of red houses are even.

Examples

Example 1

1
2
3

Input: gems = [1, 2, 0, 4, 5, 6, 2, 3], colors = [0, 0, 1, 1, 1, 0, 0, 1]
Output: 20
Explanation: Red houses are with value 1. So, we take house 3 and 4, and hence color is 4*5.

Solution

This is similar to maximum product subarray, but there is another condition of red color.

Method 1

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

public class Solution {
    public int maxGemsWithEvenReds(int[] gems, int[] colors) {
        int n = gems.length;
        int maxProduct = Integer.MIN_VALUE;

        // Prefix products and red house counts
        int[] prefixProduct = new int[n + 1];
        int[] prefixReds = new int[n + 1];
        prefixProduct[0] = 1;

        for (int i = 0; i < n; i++) {
            prefixProduct[i + 1] =
                gems[i] != 0 ? prefixProduct[i] * gems[i] : 1;
            prefixReds[i + 1] = prefixReds[i] + (colors[i] == 1 ? 1 : 0);
        }

        // Check different ranges to find the maximum product with even red
        // house count
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int redCount = prefixReds[j + 1] - prefixReds[i];
                if (redCount % 2 == 0) {
                    int product = 1;
                    for (int k = i; k <= j; k++) {
                        if (gems[k] != 0) {
                            product *= gems[k];
                        }
                    }
                    if (product > maxProduct) {
                        maxProduct = product;
                    }
                }
            }
        }

        return maxProduct;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] gems = {1, 2, 0, 4, 5, 6, 2, 3};
        int[] colors = {0, 0, 1, 1, 1, 0, 0, 1};
        System.out.println(
            solution.maxGemsWithEvenReds(gems, colors)); // Output: 20
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

def max_gems_with_even_reds(gems, colors):
    n = len(gems)
    max_product = float("-inf")

    # Prefix and suffix products and red house counts
    prefix_product = [1] * (n + 1)
    prefix_reds = [0] * (n + 1)

    for i in range(n):
        prefix_product[i + 1] = (
            prefix_product[i] * gems[i] if gems[i] != 0 else 1
        )
        prefix_reds[i + 1] = prefix_reds[i] + (1 if colors[i] == 1 else 0)

    # Check different ranges to find the maximum product with even red house count
    for i in range(n):
        for j in range(i, n):
            red_count = prefix_reds[j + 1] - prefix_reds[i]
            if red_count % 2 == 0:
                product = 1
                for k in range(i, j + 1):
                    if gems[k] != 0:
                        product *= gems[k]
                if product > max_product:
                    max_product = product

    return max_product


# Example usage
gems = [1, 2, 0, 4, 5, 6, 2, 3]
colors = [0, 0, 1, 1, 1, 0, 0, 1]
print(max_gems_with_even_reds(gems, colors))  # Output: 20

Complexity

  • ⏰ Time complexity: O(n^2), because we have two nested loops to check all possible subarrays/ranges, and within those loops, we may compute the product which has O(n) complexity in the worst case.
  • 🧺 Space complexity: O(n), due to the arrays used for prefix products and counts of red houses.