Prerequisites
Before attempting this problem, you should be comfortable with:
- Hash Maps - Using dictionaries to group and track maximum values by key
- Sorting - Sorting values to find the top k elements efficiently
- Heaps/Priority Queues - Maintaining the k largest elements using a min-heap of fixed size
1. Hash Map
Intuition
We need to pick three indices with distinct x-values and maximize the sum of their corresponding y-values. For each unique x-value, we only care about the maximum y-value associated with it, since choosing a smaller y-value for the same x would never be optimal.
After collecting the best y-value for each distinct x, we simply need the three largest values. If there are fewer than three distinct x-values, the answer is -1.
Algorithm
- Build a hash map where each key is an x-value and the value is the maximum y-value seen for that x.
- If the map has fewer than
3entries, return-1. - Extract all the y-values from the map and sort them.
- Return the sum of the three largest y-values.
Time & Space Complexity
- Time complexity:
- Space complexity:
2. Hash Map + Min-Heap
Intuition
Instead of sorting all values to find the top 3, we can use a min-heap of size 3. As we iterate through the distinct y-values, we maintain only the three largest seen so far. This avoids the overhead of sorting the entire collection.
Whenever the heap exceeds size 3, we remove the smallest element. After processing all values, the heap contains exactly the three largest y-values (if at least 3 exist).
Algorithm
- Build a hash map mapping each x-value to its maximum y-value.
- Initialize an empty min-heap.
- For each y-value in the map:
- Push it onto the heap.
- If heap size exceeds
3, pop the minimum.
- If the heap has fewer than
3elements, return-1. - Return the sum of all elements in the heap.
class Solution:
def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
mp = {}
for xi, yi in zip(x, y):
mp[xi] = max(mp.get(xi, 0), yi)
minHeap = []
for val in mp.values():
heapq.heappush(minHeap, val)
if len(minHeap) > 3:
heapq.heappop(minHeap)
return -1 if len(minHeap) < 3 else sum(minHeap)Time & Space Complexity
- Time complexity:
- Space complexity:
3. Greedy
Intuition
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.
Algorithm
- 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.
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 -1Time & Space Complexity
- Time complexity:
- Space complexity:
Common Pitfalls
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.