Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

What is this problem about?

Note: This title maps to a specific combinatorial logic problem. You are given an array of points, each with an X and Y coordinate. You must select exactly three points. The constraints are: all three points must have strictly distinct X coordinates. Your goal is to maximize the sum of their Y coordinates.

Why is this asked in interviews?

This is a Sorting and Heaps problem. Interviewers ask it to test your data organization skills. A brute force $O(N^3)$ approach evaluating every triplet will fail. It evaluates whether you recognize that, for any given X coordinate, only the point with the absolute highest Y value matters. Once filtered, you just need to pick the three highest Y values.

Algorithmic pattern used

This problem relies on a Hash Map Filtering and Sorting / Priority Queue pattern.

1. Since the X coordinates must be distinct, if there are multiple points with the same X coordinate, you should greedily only keep the one with the highest Y coordinate. All others are useless. Use a Hash Map to store X -> Max_Y.
2. Extract all the maximum Y values from the Hash Map into a list.
3. If the list has fewer than 3 elements, it's impossible to form a valid triplet (return 0 or -1).
4. Otherwise, sort the list in descending order (or use a Min Heap of size 3) and sum the top three Y values.

Example explanation

Points: [(1, 10), (1, 20), (2, 5), (3, 15), (2, 30)] Step 1: Filter by max Y for each X using a Hash Map.

• X=1: Max Y is 20. Map: {1: 20}.
• X=2: Max Y is 30. Map: {1: 20, 2: 30}.
• X=3: Max Y is 15. Map: {1: 20, 2: 30, 3: 15}.

Step 2: Extract Y values. Values: [20, 30, 15].

Step 3: Sort descending and take top 3. Sorted: [30, 20, 15]. Sum = $30 + 20 + 15 = 65$. This sum is guaranteed to come from distinct X values because our Hash Map enforced that constraint globally.

Common mistakes candidates make

Candidates often try to sort the original array by Y descending, and then use three pointers or a while loop to find the first three points with different X values. While this works and is $O(N \log N)$, the Hash Map approach is $O(N)$ time complexity and vastly easier to implement correctly without risking messy while loop index bounds.

Interview preparation tip

When an interview question asks to maximize a value subject to a "distinct ID" or "distinct category" constraint, your very first instinct should be a Hash Map grouping. Squashing the data down to Category -> Best Value instantly eliminates the complexity of the constraint, allowing you to focus purely on the optimization goal.