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

• Preprocessing:
  1. Create a HashMap<Integer, Integer> called max_y_for_x to store the maximum y value for each unique x coordinate.
  2. Iterate through the input arrays x and y. For each pair (x[i], y[i]), update the map: max_y_for_x.put(x[i], Math.max(max_y_for_x.getOrDefault(x[i], 0), y[i])).
• Feasibility Check:
  1. If the number of unique x values (max_y_for_x.size()) is less than 3, return -1.
• Brute-Force Triplet Selection:
  1. Convert the map's entries into a List of pairs, let's call it points.
  2. Initialize a variable maxSum to -1.
  3. Use three nested loops to iterate through all unique combinations of three points from the points list.
  4. For each combination, calculate the sum of their y values.
  5. Update maxSum if the current sum is greater.
• Return Result:
  1. Return maxSum.

The core idea is to first reduce the problem space. Since we need to pick three points with distinct x coordinates, for any given x coordinate that appears multiple times, we only ever need to consider the point with the highest y coordinate. This is because picking any other point with the same x coordinate would result in a smaller or equal sum.

1. Preprocessing: We iterate through the n points and use a HashMap to store the maximum y value seen for each x value. The key of the map is the x coordinate, and the value is the maximum y coordinate found for it.
2. Triplet Search: After populating the map, we have a set of unique x coordinates and their corresponding best y values. If this set has fewer than three entries, it's impossible to form a valid triplet, so we return -1. Otherwise, we convert the map entries to a list and use a brute-force method with three nested loops to check every possible combination of three distinct entries. For each combination, we sum their y values and update our overall maximum sum.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public long maximumTripletValue(int[] x, int[] y) {8        Map<Integer, Integer> maxYForX = new HashMap<>();9        for (int i = 0; i < x.length; i++) {10            maxYForX.put(x[i], Math.max(maxYForX.getOrDefault(x[i], 0), y[i]));11        }12 13        if (maxYForX.size() < 3) {14            return -1;15        }16 17        List<Map.Entry<Integer, Integer>> points = new ArrayList<>(maxYForX.entrySet());18        long maxSum = -1;19        int m = points.size();20 21        for (int i = 0; i < m; i++) {22            for (int j = i + 1; j < m; j++) {23                for (int k = j + 1; k < m; k++) {24                    long currentSum = (long) points.get(i).getValue() +25                                      points.get(j).getValue() +26                                      points.get(k).getValue();27                    if (maxSum == -1 || currentSum > maxSum) {28                        maxSum = currentSum;29                    }30                }31            }32        }33        return maxSum;34    }35}