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

Med

#3180Time: 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.

Patterns

Greedy

Algorithms

Sorting

Data structures

Array Hash Table Heap (Priority Queue)

Prompt

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 <= 10⁵
1 <= x[i], y[i] <= 10⁶

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

Preprocessing: Use a HashMap to find the maximum y for each x in O(n) time.
Feasibility Check: Ensure there are at least three unique x values.
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.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.HashMap;4import java.util.List;5import java.util.Map;6 7class Solution {8    public long maximumTripletValue(int[] x, int[] y) {9        Map<Integer, Integer> maxYForX = new HashMap<>();10        for (int i = 0; i < x.length; i++) {11            maxYForX.put(x[i], Math.max(maxYForX.getOrDefault(x[i], 0), y[i]));12        }13 14        if (maxYForX.size() < 3) {15            return -1;16        }17 18        List<Integer> yValues = new ArrayList<>(maxYForX.values());19        Collections.sort(yValues, Collections.reverseOrder());20 21        return (long) yValues.get(0) + yValues.get(1) + yValues.get(2);22    }23}

Complexity

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

Trade-offs

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.

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.

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.

Walkthrough

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.

Preprocessing: We perform the same initial step of using a HashMap to find the maximum y for each unique x in O(n) time.
Feasibility Check: We ensure there are at least three unique x values.
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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long maximumTripletValue(int[] x, int[] y) {6        Map<Integer, Integer> maxYForX = new HashMap<>();7        for (int i = 0; i < x.length; i++) {8            maxYForX.put(x[i], Math.max(maxYForX.getOrDefault(x[i], 0), y[i]));9        }10 11        if (maxYForX.size() < 3) {12            return -1;13        }14 15        long firstMax = 0, secondMax = 0, thirdMax = 0;16        for (int val : maxYForX.values()) {17            if (val > firstMax) {18                thirdMax = secondMax;19                secondMax = firstMax;20                firstMax = val;21            } else if (val > secondMax) {22                thirdMax = secondMax;23                secondMax = val;24            } else if (val > thirdMax) {25                thirdMax = val;26            }27        }28 29        return firstMax + secondMax + thirdMax;30    }31}

Complexity

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

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem