Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values solution and explanation
6 more videos on this problem
3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values | Biweekly Contest 158 | LeetcodeRapid Syntax · 11:57 · 316 views
3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values (Leetcode Medium)Programming Live with Larry · 6:21 · 251 views
3572. Maximize Y-Sum by Picking a Triplet of Distinct X-Values | BiWeekly Contest 158Tech Courses · 6:10 · 229 views
LeetCode 3572: Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values | Java Solution |Code Scribbler · 5:18 · 51 views
LeetCode 3572: Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values | Python SolutionCode Scribbler · 5:15 · 34 views
LeetCode 3572: Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values | CSharp Solution |Code Scribbler · 5:28 · 33 views
3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values | Java | Biweekly Contest 158ExpertFunda · 13:15 · 16 views
The problem
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
Approach overview
Problem Overview: You are given pairs of (x, y). The goal is to pick exactly three elements such that their x values are all different and the total y sum is maximized. The challenge is enforcing the distinct x constraint while still selecting the three largest possible y values.
Approach 1: Brute Force Triplets (O(n^3) time, O(1) space)
Check every combination of three indices using three nested loops. For each triplet, verify that the three x values are distinct and compute the sum of their y values. Track the maximum valid sum found. This method directly models the problem but becomes impractical for large inputs because the number of triplets grows cubically.
Approach 2: Hash Table + Sorting (O(n log n) time, O(n) space)
Only one element per x can appear in the final triplet. That means for each distinct x, you only care about the maximum y. Use a hash table to map each x to the largest y seen while iterating through the input. After building this map, collect the values and sort them in descending order using sorting. The answer is the sum of the top three values if at least three unique x exist. This reduces the search space from n elements to the number of unique x values.
Approach 3: Hash Table + Min Heap (O(n log k) time, O(n) space)
The map-building step remains the same: iterate once and store the best y for every x. Instead of sorting all values, maintain a size‑3 min heap using a heap (priority queue). Push each candidate y into the heap and remove the smallest whenever the heap grows beyond three elements. After processing all values, the heap contains the three largest y values from distinct x keys. This avoids sorting the entire list and keeps only the necessary candidates.
Recommended for interviews: Interviewers typically expect the hash table reduction followed by sorting or a small heap. Recognizing that each x contributes at most one useful candidate is the key greedy insight. Mentioning the brute force approach shows baseline reasoning, but implementing the hash map + sorting or heap solution demonstrates strong optimization skills.
Solution
We pair the elements of arrays x and y into a 2D array arr, and then sort 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 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 x and y.
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 -1class 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;
}
}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;
}
};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;
}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
}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
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplets | O(n^3) | O(1) | Small inputs or initial reasoning during interviews |
| Hash Table + Sorting | O(n log n) | O(n) | General solution when extracting top values after grouping by x |
| Hash Table + Min Heap (Top 3) | O(n log 3) ≈ O(n) | O(n) | When only the top 3 values are needed and you want to avoid full sorting |
Frequently asked questions
Is Maximize Y-Sum by Picking a Triplet of Distinct X-Values easy or hard?
The problem is generally rated Medium because the brute force idea is simple but inefficient. Recognizing that only the best y per x matters and then selecting the top three values requires a combination of greedy thinking and efficient data structures.
Maximize Y-Sum by Picking a Triplet of Distinct X-Values Python/Java solution
Most implementations first build a dictionary or map where each x stores the largest y seen. After that, either sort the values and sum the top three or use a priority queue of size three. This approach works consistently across Python, Java, C++, Go, and TypeScript.
How to solve Maximize Y-Sum by Picking a Triplet of Distinct X-Values in O(n)?
First iterate through the array and use a hash map to keep the maximum y for each x. Then push those values into a min heap of size 3, removing the smallest whenever the heap exceeds three elements. This keeps only the three largest y values from distinct x keys and runs in O(n log 3) ≈ O(n).
What is the best approach for Maximize Y-Sum by Picking a Triplet of Distinct X-Values?
The most practical solution uses a hash table to store the maximum y value for each distinct x, then selects the top three values. This can be done by sorting the values (O(n log n)) or maintaining a min heap of size 3 (O(n log 3)). The key insight is that each x can contribute only one candidate to the final triplet.
Is Maximize Y-Sum by Picking a Triplet of Distinct X-Values asked at Google/Amazon/Meta?
Problems combining hash tables, greedy selection, and top-k elements frequently appear in interviews at companies like Amazon and Google. Variants involving grouping by key and selecting maximum values are common in coding rounds and online assessments.
What data structure is used in Maximize Y-Sum by Picking a Triplet of Distinct X-Values?
The core data structures are a hash table for grouping values by x and either sorting or a min heap (priority queue) to extract the top three y values. These structures enforce the distinct-x constraint while efficiently identifying the best candidates.
What is the time complexity of Maximize Y-Sum by Picking a Triplet of Distinct X-Values?
The optimal approach runs in O(n log n) time when sorting the candidate values after building a hash map of best y per x. Using a fixed-size heap reduces the selection step to O(n log 3), which is effectively O(n). Space complexity is O(n) for storing the x to max-y mapping.