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

1. Build a hash map where each key is an x-value and the value is the maximum y-value seen for that x.
2. If the map has fewer than 3 entries, return -1.
3. Extract all the y-values from the map and sort them.
4. Return the sum of the three largest y-values.

class Solution:
    def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
        mp = {}

        for i in range(len(x)):
            if x[i] not in mp:
                mp[x[i]] = y[i]
            
            mp[x[i]] = max(mp[x[i]], y[i])

        return -1 if len(mp) < 3 else sum(sorted(list(mp.values()))[-3:])

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(n)$

---

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

1. Build a hash map mapping each x-value to its maximum y-value.
2. Initialize an empty min-heap.
3. For each y-value in the map:
   • Push it onto the heap.
   • If heap size exceeds 3, pop the minimum.
4. If the heap has fewer than 3 elements, return -1.
5. 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: $O(n)$
• Space complexity: $O(n)$

---

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

1. Maintain an array best of 3 pairs (x, y), initialized with sentinel values (like negative infinity for y).
2. For each (xi, yi) in the input:
   • If xi matches any x in best, update that entry's y-value if yi is larger, then re-sort.
   • Otherwise, insert (xi, yi) into the appropriate position if yi is larger than any of the current top 3 values.
3. If the smallest y-value in best is still a sentinel, return -1.
4. 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 -1

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$