Skip to content

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

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.

 

Example 1:

Input: x = [1,2,1,3,2], y = [5,3,4,6,2]

Output: 14

Explanation:

  • Choose i = 0 (x[i] = 1, y[i] = 5), j = 1 (x[j] = 2, y[j] = 3), k = 3 (x[k] = 3, y[k] = 6).
  • All three values chosen from x are distinct. 5 + 3 + 6 = 14 is the maximum we can obtain. Hence, the output is 14.

Example 2:

Input: x = [1,2,1,2], y = [4,5,6,7]

Output: -1

Explanation:

  • There are only two distinct values in x. Hence, the output is -1.

 

Constraints:

  • n == x.length == y.length
  • 3 <= n <= 105
  • 1 <= x[i], y[i] <= 106

Solutions

Solution 1: Sorting + Greedy + Hash Table

Thinking

The three \(x\) values must be distinct and the objective is the sum of their \(y\)’s, so each chosen \(x\) should contribute its best \(y\). Sort pairs by \(y\) descending, record used \(x\) in a set, and add the first three new \(x\) values.

If fewer than three distinct \(x\) appear, return \(-1\). One sort and one scan suffice.

We pair the elements of arrays \(x\) and \(y\) into a 2D array \(\textit{arr}\), and then sort \(\textit{arr}\) in descending order by the value of \(y\). Next, we use a hash table to record the \(x\) values that have already been selected, and iterate through \(\textit{arr}\), each time selecting an \(x\) value and its corresponding \(y\) value that has not been chosen yet, until we have selected three distinct \(x\) values.

If we manage to select three different \(x\) values during the iteration, we return the sum of their corresponding \(y\) values; if we finish iterating without selecting three distinct \(x\) values, we return -1.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\), where \(n\) is the length of arrays \(\textit{x}\) and \(\textit{y}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
        arr = [(a, b) for a, b in zip(x, y)]
        arr.sort(key=lambda x: -x[1])
        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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxSumDistinctTriplet(int[] x, int[] y) {
        int n = x.length;
        int[][] arr = new int[n][0];
        for (int i = 0; i < n; i++) {
            arr[i] = new int[] {x[i], y[i]};
        }
        Arrays.sort(arr, (a, b) -> b[1] - a[1]);
        int ans = 0;
        Set<Integer> vis = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            int a = arr[i][0], b = arr[i][1];
            if (vis.add(a)) {
                ans += b;
                if (vis.size() == 3) {
                    return ans;
                }
            }
        }
        return -1;
    }
}

 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
class Solution {
public:
    int maxSumDistinctTriplet(vector<int>& x, vector<int>& y) {
        int n = x.size();
        vector<array<int, 2>> arr(n);
        for (int i = 0; i < n; ++i) {
            arr[i] = {x[i], y[i]};
        }
        ranges::sort(arr, [](auto& a, auto& b) {
            return b[1] < a[1];
        });
        int ans = 0;
        unordered_set<int> vis;
        for (int i = 0; i < n; ++i) {
            int a = arr[i][0], b = arr[i][1];
            if (vis.insert(a).second) {
                ans += b;
                if (vis.size() == 3) {
                    return ans;
                }
            }
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxSumDistinctTriplet(x []int, y []int) int {
    n := len(x)
    arr := make([][2]int, n)
    for i := 0; i < n; i++ {
        arr[i] = [2]int{x[i], y[i]}
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i][1] > arr[j][1]
    })
    ans := 0
    vis := make(map[int]bool)
    for i := 0; i < n; i++ {
        a, b := arr[i][0], arr[i][1]
        if !vis[a] {
            vis[a] = true
            ans += b
            if len(vis) == 3 {
                return ans
            }
        }
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function maxSumDistinctTriplet(x: number[], y: number[]): number {
    const n = x.length;
    const arr: [number, number][] = [];
    for (let i = 0; i < n; i++) {
        arr.push([x[i], y[i]]);
    }
    arr.sort((a, b) => b[1] - a[1]);
    const vis = new Set<number>();
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const [a, b] = arr[i];
        if (!vis.has(a)) {
            vis.add(a);
            ans += b;
            if (vis.size === 3) {
                return ans;
            }
        }
    }
    return -1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn max_sum_distinct_triplet(x: Vec<i32>, y: Vec<i32>) -> i32 {
        let n = x.len();
        let mut arr: Vec<(i32, i32)> = (0..n).map(|i| (x[i], y[i])).collect();
        arr.sort_by(|a, b| b.1.cmp(&a.1));
        let mut vis = std::collections::HashSet::new();
        let mut ans = 0;
        for (a, b) in arr {
            if vis.insert(a) {
                ans += b;
                if vis.len() == 3 {
                    return ans;
                }
            }
        }
        -1
    }
}

Comments