# Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-ysum-by-picking-a-triplet-of-distinct-xvalues)
Canonical: https://scaleengineer.com/dsa/problems/maximize-ysum-by-picking-a-triplet-of-distinct-xvalues
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
---
## Problem
You are given two integer arrays `x` and `y`, each of length `n`. You must choose three **distinct** indices `i`, `j`, and `k` such that:

* `x[i] != x[j]`
* `x[j] != x[k]`
* `x[k] != x[i]`

Your goal is to **maximize** the value of `y[i] + y[j] + y[k]` under these conditions. Return the **maximum** possible sum that can be obtained by choosing such a triplet of indices.

If no such triplet exists, return -1.

**Example 1:**

**Input:** x = \[1,2,1,3,2\], y = \[5,3,4,6,2\]

**Output:** 14

**Explanation:**

* Choose `i = 0` (`x[i] = 1`, `y[i] = 5`), `j = 1` (`x[j] = 2`, `y[j] = 3`), `k = 3` (`x[k] = 3`, `y[k] = 6`).
* All three values chosen from `x` are distinct. `5 + 3 + 6 = 14` is the maximum we can obtain. Hence, the output is 14.

**Example 2:**

**Input:** x = \[1,2,1,2\], y = \[4,5,6,7\]

**Output:** \-1

**Explanation:**

* There are only two distinct values in `x`. Hence, the output is -1.

**Constraints:**

* `n == x.length == y.length`
* `3 <= n <= 105`
* `1 <= x[i], y[i] <= 106`

# Approaches
## Brute Force with Preprocessing
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.
**Time:** O(n + m^3), where `n` is the length of the input arrays and `m` is the number of unique `x` values. The preprocessing step takes O(n). The three nested loops take O(m^3). In the worst case, `m` can be up to `n`, leading to a time complexity of O(n^3). · **Space:** O(m), where `m` is the number of unique `x` values. In the worst case, all `x` values are unique, so `m = n`, leading to O(n) space complexity for the map and the list.
**Pros:** Conceptually simple and easy to understand.; The preprocessing step correctly simplifies the problem.
**Cons:** Extremely inefficient due to the cubic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   **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`.

## Sorting after Preprocessing
This approach improves upon the brute-force method by recognizing that we don't need to check every combination. After preprocessing the data to find the maximum `y` for each unique `x` (as in the previous approach), the problem reduces to finding the three largest `y` values from the resulting collection. A straightforward way to do this is to extract all the maximum `y` values, put them into a list, sort the list in descending order, and then sum the top three values.
**Time:** O(n + m log m), where `n` is the length of the input arrays and `m` is the number of unique `x` values. Preprocessing takes O(n). Sorting the `m` unique y-values takes O(m log m). In the worst case, `m=n`, leading to O(n log n). · **Space:** O(m), where `m` is the number of unique `x` values. This space is used for the map and the list of y-values. In the worst case, `m=n`, so the space complexity is O(n).
**Pros:** Significantly more efficient than the brute-force approach.; Passes the time limits for the given constraints.; Relatively simple to implement using standard library functions.
**Cons:** The sorting step is slightly suboptimal, as we only need the top three elements, not the entire sorted order.
### Explanation
Similar to the first approach, we begin by preprocessing the input to find the maximum `y` for each unique `x`. This gives us a set of pairs `(x, y_max)` where all `x` are distinct. The problem is now to pick three of these pairs to maximize the sum of their `y_max` values. Since all `x` values are already distinct, we just need to find the three largest `y_max` values.

1.  **Preprocessing:** Use a `HashMap` to find the maximum `y` for each `x` in O(n) time.
2.  **Feasibility Check:** Ensure there are at least three unique `x` values.
3.  **Extract and Sort:** Instead of a cubic-time search, we can extract all the `y_max` values from our map into a list. Then, we sort this list. The three largest values will be at the beginning of the list if sorted in descending order (or at the end if sorted in ascending order). Summing these three gives the maximum possible sum.

```java
import java.util.ArrayList;
import java.util.Collections;
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<Integer> yValues = new ArrayList<>(maxYForX.values());
        Collections.sort(yValues, Collections.reverseOrder());

        return (long) yValues.get(0) + yValues.get(1) + yValues.get(2);
    }
}
```
### Algorithm
*   **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.
*   **Sort and Sum:**
    1.  Extract all the values (the maximum `y`'s) from the map into a `List`.
    2.  Sort this list in descending order.
    3.  The result is the sum of the first three elements in the sorted list.
*   **Return Result:**
    1.  Return the calculated sum.

## Optimal Linear Time Solution
This is the most efficient approach. It builds upon the same preprocessing step but avoids the O(m log m) sorting cost. Instead of sorting all the unique maximum `y` values, we can find the three largest values in a single pass (linear time). We maintain three variables to keep track of the first, second, and third largest `y` values encountered so far. By iterating through the preprocessed `y` values just once, we can identify the top three and calculate their sum.
**Time:** O(n + m), where `n` is the length of the input arrays and `m` is the number of unique `x` values. Preprocessing is O(n), and the linear scan is O(m). In the worst case, `m=n`, so the total time complexity is O(n). · **Space:** O(m), where `m` is the number of unique `x` values, for the map. In the worst case, `m=n`, so the space complexity is O(n).
**Pros:** Optimal time complexity.; Most efficient solution for the given constraints.; Avoids the overhead of sorting the entire collection of values.
**Cons:** The logic for tracking the top three elements in a single pass is slightly more complex to write than simply calling a sort function.
### Explanation
This optimal solution refines the previous approach by eliminating the need for sorting. Finding the top three elements in a collection does not require a full sort.

1.  **Preprocessing:** We perform the same initial step of using a `HashMap` to find the maximum `y` for each unique `x` in O(n) time.
2.  **Feasibility Check:** We ensure there are at least three unique `x` values.
3.  **Single Pass for Top 3:** We initialize three variables, `firstMax`, `secondMax`, and `thirdMax`, to keep track of the three largest `y` values. We then iterate through the values of our map just once. For each value, we check if it's larger than `firstMax`, `secondMax`, or `thirdMax` and update the variables accordingly. This allows us to find the top three values in O(m) time, where `m` is the number of unique `x` values.

This avoids the O(m log m) sorting step, leading to a total time complexity of O(n + m), which simplifies to O(n) in the worst case.

```java
import java.util.HashMap;
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;
        }

        long firstMax = 0, secondMax = 0, thirdMax = 0;
        for (int val : maxYForX.values()) {
            if (val > firstMax) {
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = val;
            } else if (val > secondMax) {
                thirdMax = secondMax;
                secondMax = val;
            } else if (val > thirdMax) {
                thirdMax = val;
            }
        }

        return firstMax + secondMax + thirdMax;
    }
}
```
### Algorithm
*   **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.
*   **Linear Scan for Top 3:**
    1.  Initialize three variables: `firstMax`, `secondMax`, `thirdMax` to 0.
    2.  Iterate through the values (the maximum `y`'s) of the map.
    3.  In each iteration, compare the current value with the three tracked maximums and update them accordingly to maintain the top three values seen so far.
*   **Return Result:**
    1.  Return the sum `firstMax + secondMax + thirdMax`.