3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values
Medium63.2% acceptance30,586 / 48,382 submissions
Asked by 1 company
Topics
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
xare distinct.5 + 3 + 6 = 14is 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.length3 <= n <= 1051 <= x[i], y[i] <= 106
Hints
Hint 1
For each unique
x, keep only the maximum y; all other pairs with the same x are redundant.Hint 2
Sort the pairs by
x so that identical x values form contiguous blocks, then take the maximum y from each block.Hint 3
Alternatively, use a map (or dictionary) from
x to its largest y.