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

This approach first simplifies the problem by preprocessing the input arrays. We are interested in maximizing the sum of y values for three distinct x values. If multiple points share the same x coordinate, we only need to consider the one with the largest y value for that x. We can use a hash map to store the maximum y for each unique x. After preprocessing, we have a collection of unique (x, y_max) pairs. Then, we can iterate through all possible combinations of three pairs from this collection, calculate their y-sum, and keep track of the maximum sum found.

• 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.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public long maximumTripletValue(int[] x, int[] y) {
        Map<Integer, Integer> maxYForX = new HashMap<>();
        for (int i = 0; i < x.length; i++) {
            maxYForX.put(x[i], Math.max(maxYForX.getOrDefault(x[i], 0), y[i]));
        }

        if (maxYForX.size() < 3) {
            return -1;
        }

        List<Map.Entry<Integer, Integer>> points = new ArrayList<>(maxYForX.entrySet());
        long maxSum = -1;
        int m = points.size();

        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                for (int k = j + 1; k < m; k++) {
                    long currentSum = (long) points.get(i).getValue() +
                                      points.get(j).getValue() +
                                      points.get(k).getValue();
                    if (maxSum == -1 || currentSum > maxSum) {
                        maxSum = currentSum;
                    }
                }
            }
        }
        return maxSum;
    }
}