3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

MediumGreedyArrayHash TableSortingHeap (Priority Queue)

Problem Description

You are given two integer arrays x and y, each of length n. You must choose three distinct indices i, j, and k such that:

x[i] != x[j]
x[j] != x[k]
x[k] != x[i]

Your goal is to maximize the value of y[i] + y[j] + y[k] under these conditions. Return the maximum possible sum that can be obtained by choosing such a triplet of indices.

If no such triplet exists, return -1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The goal is to pick three indices where all their corresponding x values are different, and make the sum of the y values as large as possible. To get the largest possible sum, we should try to choose the largest available y values, but every x has to be unique among the chosen ones. So, if we go through the pairs (x[i], y[i]) sorted from highest to lowest y[i] values, and each time pick a pair whose x value hasn't been picked before, we can quickly find the best option. As soon as we've picked three distinct x values, we can stop and sum up their y values. If we can't find three such x values, then it's not possible to form the triplet. This lets us solve the problem efficiently by prioritizing high y values while making sure all x values are different.

Solution Approach

The solution uses a combination of sorting, a greedy selection strategy, and a hash set to ensure uniqueness of the selected x values.

Pairing and Sorting: First, pair each value from x with its corresponding value from y to get a list of tuples. Then, sort these pairs in descending order based on the y values. This way, higher y values come first, maximizing the sum as we pick elements.

Example code:
```
arr = [(a, b) for a, b in zip(x, y)]
arr.sort(key=lambda x: -x[1])
```

Selecting Unique x Values: Use a set to keep track of x values that have already been chosen. Iterate through the sorted list and select a pair only if its x value is not in the set. Each time a new unique x is picked, add its y value to the current sum.

Example pattern:

vis = set()
ans = 0
for a, b in arr:
    if a in vis:
        continue
    vis.add(a)
    ans += b
    if len(vis) == 3:
        return ans
return -1

Early Termination: Once three distinct x values are selected, immediately return the running sum of their y values. If all pairs are checked without finding three unique x values, return -1.

This approach works efficiently because sorting ensures we always consider the largest y values first, and the set guarantees that all chosen x values are distinct.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Suppose x = [1, 2, 1, 3, 4] and y = [10, 20, 15, 9, 8].

Step 1: Pair and Sort

Pair the values: [(1, 10), (2, 20), (1, 15), (3, 9), (4, 8)]
Sort by y in descending order: Result: [(2, 20), (1, 15), (1, 10), (3, 9), (4, 8)]

Step 2: Select pairs with unique x

Start an empty set vis = {} and ans = 0
Check (2, 20): 2 not in vis, add 2 and add 20 to sum (ans = 20)
- vis = {2}
Check (1, 15): 1 not in vis, add 1 and add 15 to sum (ans = 35)
- vis = {1, 2}
Check (1, 10): 1 is already in vis, skip
Check (3, 9): 3 not in vis, add 3 and add 9 to sum (ans = 44)
- vis = {1, 2, 3}

Step 3: Early Termination

We have three unique x values (1, 2, 3), so we stop and return the sum 44.

Conclusion: The maximum sum achievable by picking indices with all different x values is 44.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
5        # Pair elements from x and y, creating a list of (value, weight) tuples
6        pairs = [(a, b) for a, b in zip(x, y)]
7
8        # Sort the pairs descending by 'weight' (the second item in the tuple)
9        pairs.sort(key=lambda item: -item[1])
10
11        # Set to keep track of unique 'value's selected
12        used_values = set()
13
14        total_sum = 0
15
16        # Traverse each pair in descending order of 'weight'
17        for value, weight in pairs:
18            # Skip if 'value' is already used to maintain distinctness
19            if value in used_values:
20                continue
21            # Mark 'value' as used
22            used_values.add(value)
23            # Add 'weight' to the sum
24            total_sum += weight
25            # If we have 3 distinct values, return the sum
26            if len(used_values) == 3:
27                return total_sum
28        # Not enough distinct values found, return -1
29        return -1
30

1class Solution {
2    public int maxSumDistinctTriplet(int[] keys, int[] values) {
3        int n = keys.length;
4
5        // Create a pair array: each element holds a key and its corresponding value
6        int[][] pairs = new int[n][2];
7        for (int i = 0; i < n; i++) {
8            pairs[i][0] = keys[i];
9            pairs[i][1] = values[i];
10        }
11
12        // Sort the pairs array in descending order based on value
13        Arrays.sort(pairs, (a, b) -> b[1] - a[1]);
14
15        int sum = 0;
16        Set<Integer> distinctKeys = new HashSet<>();
17
18        // Iterate over the sorted pairs, collecting up to 3 distinct keys with max total value
19        for (int i = 0; i < n; i++) {
20            int key = pairs[i][0];
21            int value = pairs[i][1];
22            if (distinctKeys.add(key)) {
23                sum += value;
24                // Stop once 3 distinct keys are found
25                if (distinctKeys.size() == 3) {
26                    return sum;
27                }
28            }
29        }
30
31        // If fewer than 3 distinct keys exist, return -1
32        return -1;
33    }
34}
35

1class Solution {
2public:
3    int maxSumDistinctTriplet(vector<int>& x, vector<int>& y) {
4        int n = x.size();
5        // Combine x and y into pairs (x[i], y[i])
6        vector<pair<int, int>> pairs(n);
7        for (int i = 0; i < n; ++i) {
8            pairs[i] = {x[i], y[i]};
9        }
10
11        // Sort pairs in descending order based on y[i]
12        sort(pairs.begin(), pairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
13            return a.second > b.second;
14        });
15
16        int answer = 0;
17        unordered_set<int> seen;
18        // Select up to 3 different x-values with largest y-values
19        for (int i = 0; i < n; ++i) {
20            int xi = pairs[i].first;
21            int yi = pairs[i].second;
22            // If this x-value is not taken, add its y to answer
23            if (seen.insert(xi).second) {
24                answer += yi;
25                // Stop when we have 3 distinct x-values
26                if (seen.size() == 3) {
27                    return answer;
28                }
29            }
30        }
31        // Return -1 if not enough distinct x-values
32        return -1;
33    }
34};
35

1/**
2 * Finds the maximum sum of values y corresponding to three distinct x values.
3 * If fewer than three distinct x values exist, returns -1.
4 *
5 * @param x - The array containing x values.
6 * @param y - The array containing y values, parallel to x.
7 * @returns The maximum sum for three distinct x values, or -1 if not possible.
8 */
9function maxSumDistinctTriplet(x: number[], y: number[]): number {
10    const n: number = x.length;
11    // Create an array of pairs [x, y].
12    const pairs: [number, number][] = [];
13    for (let i = 0; i < n; i++) {
14        pairs.push([x[i], y[i]]);
15    }
16    // Sort pairs descending by the y value.
17    pairs.sort((a, b) => b[1] - a[1]);
18
19    const seenX: Set<number> = new Set();
20    let sum: number = 0;
21
22    // Traverse sorted pairs, ensuring unique x values in result.
23    for (let i = 0; i < n; i++) {
24        const [currX, currY] = pairs[i];
25        if (!seenX.has(currX)) {
26            seenX.add(currX);
27            sum += currY;
28            // Stop when three distinct x values have been found.
29            if (seenX.size === 3) {
30                return sum;
31            }
32        }
33    }
34    // Not enough distinct x values found.
35    return -1;
36}
37

Time and Space Complexity

The time complexity of the code is O(n \times \log n), where n is the length of arrays x and y. This is mainly due to the sorting operation on the list arr.

The space complexity is O(n). This comes from the creation of the arr list, which stores all the (a, b) pairs from x and y, as well as the set vis.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know