Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values
Medium · Heap / Priority Queue · Explanation and code example
Greedy
How it works
We can track the top 3 candidates in constant space by maintaining a sorted list of the best 3 (x, y) pairs seen so far. For each new element, we either update an existing entry (if the x-value matches) or insert it if the y-value is large enough to make the top 3.
The key insight is that we only ever need to compare against at most 3 entries. When an x-value already exists in our top 3, we update its y-value if the new one is larger and re-sort. Otherwise, we check if the new y-value can replace the smallest of our current top 3.
Steps
- Maintain an array
bestof3pairs(x, y), initialized with sentinel values (like negative infinity for y). - For each
(xi, yi)in the input:- If
ximatches any x inbest, update that entry's y-value ifyiis larger, then re-sort. - Otherwise, insert
(xi, yi)into the appropriate position ifyiis larger than any of the current top3values.
- If
- If the smallest y-value in
bestis still a sentinel, return-1. - Return the sum of all three y-values.
Complexity
- Time complexity:
O(n) - Space complexity:
O(1)
Things to watch for
Not Taking Maximum Y for Each X
When multiple indices share the same x-value, only the maximum corresponding y-value matters. Using any y-value instead of tracking the maximum for each distinct x leads to suboptimal triplet selections.
Forgetting to Handle Fewer Than Three Distinct X-Values
If there are fewer than 3 distinct x-values in the input, no valid triplet exists. Failing to check this condition before computing the sum causes index-out-of-bounds errors or returns an invalid result instead of -1.
Python code example
from typing import List
class Solution:
def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
best = [(None, float("-inf"))] * 3
for xi, yi in zip(x, y):
for i, (xj, yj) in enumerate(best):
if xi == xj:
if yi > yj:
best[i] = (xi, yi)
best.sort(key=lambda t: t[1], reverse=True)
break
else:
if yi > best[0][1]:
best = [(xi, yi), best[0], best[1]]
elif yi > best[1][1]:
best = [best[0], (xi, yi), best[1]]
elif yi > best[2][1]:
best[2] = (xi, yi)
return sum(v for _, v in best) if best[2][1] > float("-inf") else -1
C++ code example
class Solution {
public:
int maxSumDistinctTriplet(vector<int>& x, vector<int>& y) {
vector<pair<int,int>> best(3, {INT_MIN, INT_MIN});
for (int i = 0; i < x.size(); i++) {
int xi = x[i], yi = y[i];
bool updated = false;
for (int j = 0; j < 3; j++) {
if (best[j].first == xi) {
if (yi > best[j].second) {
best[j].second = yi;
sort(best.begin(), best.end(),
[](auto &a, auto &b){ return a.second > b.second; });
}
updated = true;
break;
}
}
if (updated) continue;
if (yi > best[0].second) {
best.insert(best.begin(), {xi, yi});
best.pop_back();
} else if (yi > best[1].second) {
best.insert(best.begin()+1, {xi, yi});
best.pop_back();
} else if (yi > best[2].second) {
best[2] = {xi, yi};
}
}
if (best[2].second == INT_MIN) return -1;
return best[0].second + best[1].second + best[2].second;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.