3894. Maximize Ysum By Picking A Triplet Of Distinct Xvalues¶

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

Medium

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 <= 10⁵
1 <= x[i], y[i] <= 10⁶

Solution¶

class Solution {
    public int maxSumDistinctTriplet(int[] x, int[] y) {
        int n = x.length, m = 0;
        for (int ele : x) m = Math.max(m, ele);
        int res[] = new int[m + 1];
        HashSet<Integer> set = new HashSet<>();
        for (int ele : x) set.add(ele);
        if (set.size() < 3) return -1;
        for (int i = 0; i < n; i++) {
            res[x[i]] = Math.max(res[x[i]], y[i]);
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for (int ele : set) ans.add(res[ele]);
        Collections.sort(ans);
        return ans.get(ans.size() - 1) + ans.get(ans.size() - 2) + ans.get(ans.size() - 3);
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]