Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values - Solution & Explanation

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.