LeetCode Problem 3572

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue)

Solution

LeetCode 3572 - Maximize Y-Sum by Picking a Triplet of Distinct X-Values

Problem Understanding

The problem gives us two arrays, x and y, both of length n. Each position i represents a pair (x[i], y[i]).

We need to select exactly three distinct indices i, j, and k such that the corresponding x values are all different:

• x[i] != x[j]
• x[j] != x[k]
• x[k] != x[i]

Among all valid choices, we want to maximize:

$$y[i] + y[j] + y[k]$$

The key observation is that the restriction applies only to the values in x, not to the values in y. Multiple indices may share the same x value, but we can choose at most one of them because all three selected x values must be distinct.

The input size is quite large:

• 3 <= n <= 10^5
• 1 <= x[i], y[i] <= 10^6

A solution that examines all possible triplets would be far too slow because the number of triplets grows cubically with n.

An important way to think about the problem is that for every distinct value of x, only the largest associated y value can ever be useful. If we decide to use a particular x value in the final triplet, choosing anything other than its maximum y would never improve the answer.

Several edge cases are worth noting:

• There may be fewer than three distinct values in x, making a valid triplet impossible.
• A particular x value may appear many times, requiring us to keep only its best y.
• The maximum y values may come from duplicate x groups, so we must respect the distinctness constraint.
• Since all y[i] are positive, once we know the best y for each distinct x, the optimal answer is simply the sum of the three largest such values.

Approaches

Brute Force

A straightforward solution would enumerate every possible triplet of indices (i, j, k).

For each triplet, we would check whether the corresponding x values are pairwise distinct. If they are, we compute the sum of the three y values and update the maximum answer.

This approach is correct because it explicitly checks every valid triplet and therefore cannot miss the optimal one.

However, the number of triplets is:

$$\binom{n}{3}$$

which is O(n³). With n = 100,000, this is completely infeasible.

Optimal Approach

The distinctness condition applies only to x values.

Suppose a particular value x = v appears multiple times. If we ever choose this group, we should always take the occurrence with the largest y, because choosing a smaller y can only decrease the final sum.

Therefore:

1. Group indices by their x value.
2. For each distinct x, keep only the maximum y.
3. Collect all these maximum values.
4. If there are fewer than three distinct x values, return -1.
5. Otherwise, select the three largest group maxima and sum them.

Because all y values are positive, choosing the three largest available group maxima always yields the maximum possible triplet sum.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every triplet explicitly
Optimal	O(n)	O(m)	Keep the best y for each distinct x, where m is the number of distinct x values

Algorithm Walkthrough

1. Create a hash map where the key is an x value and the value is the maximum y seen for that x.
2. Iterate through both arrays simultaneously.
3. For each pair (x[i], y[i]), update the hash map entry:

• If this x has not been seen before, store y[i].
• Otherwise, replace the stored value if y[i] is larger.

4. After processing all elements, the hash map contains exactly one value for every distinct x, namely the largest y associated with that x.
5. Check the number of distinct x values.

• If there are fewer than three, return -1 because forming a valid triplet is impossible.

6. Extract all stored maximum y values.
7. Find the three largest values among them.
8. Return their sum.

Why it works

For any distinct x value, only the largest associated y can contribute to an optimal solution. Replacing a chosen occurrence with another occurrence having the same x but a smaller y would never increase the answer.

Therefore, each distinct x can be represented by a single number, its maximum y. The problem then becomes choosing three distinct groups whose representative values have the largest possible sum. Since all values are positive and independent after grouping, selecting the three largest representatives is optimal. Here is a detailed technical solution guide for LeetCode 3572 following your requested format:

Problem Understanding

The problem asks us to find the maximum sum of three y values corresponding to three distinct x values. We are given two arrays x and y of equal length n. Each element in x represents a category or identifier, and each element in y represents a value associated with that identifier. Our goal is to select three indices i, j, k such that x[i], x[j], and x[k] are all different, and the sum y[i] + y[j] + y[k] is maximized.

The constraints indicate that n can be as large as 10^5, meaning any solution with time complexity worse than O(n log n) may be too slow. The x[i] values can range up to 10^6, which means we cannot use an array indexed by x directly without considering memory. Edge cases include arrays where there are fewer than three distinct x values, in which case no valid triplet exists and the function should return -1.

Key points are ensuring that we only pick distinct x values, efficiently tracking the highest y values for each unique x, and handling cases where there are fewer than three unique x values.

Approaches

The brute-force approach would be to iterate over all possible triplets of indices (i, j, k), check if their x values are distinct, and compute the sum of their y values. While this is correct, it has a time complexity of O(n^3) and is infeasible for large n.

The optimal approach relies on the observation that, for each unique x value, we only need the largest y value associated with it. Once we have the largest y value for each distinct x, we can sort these values in descending order and take the top three. This ensures we pick three distinct x values while maximizing the sum. The primary insight is that any smaller y values for the same x cannot contribute to the maximum triplet sum.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks all triplets, too slow for n up to 10^5
Optimal	O(n + k log k)	O(k)	Keeps only max y per x, sorts top values; k = # of unique x

Algorithm Walkthrough

1. Initialize a hash map max_y_for_x to store the maximum y for each distinct x.
2. Iterate through all indices i from 0 to n-1. For each x[i], update max_y_for_x[x[i]] if y[i] is greater than the current stored value.
3. After processing all elements, extract the list of maximum y values corresponding to distinct x values.
4. If the number of distinct x values is less than 3, return -1 since a valid triplet cannot exist.
5. Sort the list of maximum y values in descending order.
6. Return the sum of the top three values in the sorted list.

Why it works: The hash map ensures that we only consider the largest y for each unique x, guaranteeing that the triplet we pick maximizes the sum while satisfying the distinctness constraint. Sorting ensures that we can efficiently pick the top three values.

Python Solution

from typing import List

class Solution:
    def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
        best_y = {}

        for xi, yi in zip(x, y):
            if xi not in best_y or yi > best_y[xi]:
                best_y[xi] = yi

        if len(best_y) < 3:
            return -1

        values = sorted(best_y.values(), reverse=True)
        return values[0] + values[1] + values[2]

The implementation begins by building a dictionary called best_y. For every distinct x value, the dictionary stores the largest y encountered so far.

After the scan finishes, each dictionary entry represents the best possible contribution of that x group.

The next step checks whether at least three distinct groups exist. If not, no valid triplet can be formed and the answer is -1.

Otherwise, all group maxima are collected and sorted in descending order. The first three values are the largest achievable contributions from three distinct x values, so their sum is returned. max_y_for_x = {} for xi, yi in zip(x, y): if xi not in max_y_for_x or yi > max_y_for_x[xi]: max_y_for_x[xi] = yi

    if len(max_y_for_x) < 3:
        return -1
    
    top_values = sorted(max_y_for_x.values(), reverse=True)
    return top_values[0] + top_values[1] + top_values[2]

In this implementation, the `zip` function iterates over `x` and `y` in parallel. The dictionary `max_y_for_x` stores only the largest `y` for each unique `x`. After verifying that there are at least three distinct `x` values, we sort the maximum values in descending order and sum the top three. This ensures correctness and efficiency.

## Go Solution

```go
func maxSumDistinctTriplet(x []int, y []int) int {
	bestY := make(map[int]int)

	for i := 0; i < len(x); i++ {
		if current, exists := bestY[x[i]]; !exists || y[i] > current {
			bestY[x[i]] = y[i]
		}
	}

	if len(bestY) < 3 {
		return -1
	}

	values := make([]int, 0, len(bestY))
	for _, v := range bestY {
		values = append(values, v)
	}

	sort.Slice(values, func(i, j int) bool {
		return values[i] > values[j]
	})

	return values[0] + values[1] + values[2]
}

The Go implementation follows exactly the same logic as the Python version. A map stores the largest y value for each distinct x. After collecting those values into a slice, sort.Slice sorts them in descending order and the largest three are summed.

Integer overflow is not a concern because the maximum possible answer is:

$$3 \times 10^6$$

which easily fits inside Go's int type.

Worked Examples

Example 1

Input

x = [1,2,1,3,2]
y = [5,3,4,6,2]

Building the hash map

Step	x[i]	y[i]	best_y
1	1	5	{1: 5}
2	2	3	{1: 5, 2: 3}
3	1	4	{1: 5, 2: 3}
4	3	6	{1: 5, 2: 3, 3: 6}
5	2	2	{1: 5, 2: 3, 3: 6}

The maximum y for each distinct x is:

x = 1 -> 5
x = 2 -> 3
x = 3 -> 6

Collected values:

[5, 3, 6]

Sorted descending:

[6, 5, 3]

Answer:

6 + 5 + 3 = 14

Example 2

Input

x = [1,2,1,2]
y = [4,5,6,7]

Building the hash map

Step	x[i]	y[i]	best_y
1	1	4	{1: 4}
2	2	5	{1: 4, 2: 5}
3	1	6	{1: 6, 2: 5}
4	2	7	{1: 6, 2: 7}

Final map:

{1: 6, 2: 7}

There are only two distinct x values.

Since three distinct x values are required, the answer is:

-1

import "sort"

func maxSumDistinctTriplet(x []int, y []int) int { maxY := make(map[int]int) for i := 0; i < len(x); i++ { if val, exists := maxY[x[i]]; !exists || y[i] > val { maxY[x[i]] = y[i] } }

if len(maxY) < 3 {
    return -1
}

topValues := make([]int, 0, len(maxY))
for _, v := range maxY {
    topValues = append(topValues, v)
}

sort.Sort(sort.Reverse(sort.IntSlice(topValues)))
return topValues[0] + topValues[1] + topValues[2]

}

The Go version mirrors the Python solution. The main difference is explicit handling of slices and maps. We use `sort.Reverse(sort.IntSlice(topValues))` to sort in descending order. There is no concern for `nil` slices because we initialize with `make`.

## Worked Examples

**Example 1:**

x = [1,2,1,3,2], y = [5,3,4,6,2]

| x | y | max_y_for_x update |
| --- | --- | --- |
| 1 | 5 | max_y_for_x[1] = 5 |
| 2 | 3 | max_y_for_x[2] = 3 |
| 1 | 4 | max_y_for_x[1] = 5 (unchanged) |
| 3 | 6 | max_y_for_x[3] = 6 |
| 2 | 2 | max_y_for_x[2] = 3 (unchanged) |

Top values: [6, 5, 3] → sum = 14

**Example 2:**

x = [1,2,1,2], y = [4,5,6,7]

max_y_for_x = {1:6, 2:7} → fewer than 3 distinct x → return -1

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n + m log m) | Build the hash map in O(n), sort the `m` distinct groups |
| Space | O(m) | Store one entry per distinct `x` value |

Here, `m` denotes the number of distinct values in `x`. Since `m ≤ n`, the complexity is often written as `O(n log n)` in the worst case. The hash map stores only one value per distinct `x`, resulting in `O(m)` auxiliary space.

An alternative implementation could use a size-3 min-heap to achieve `O(n)` time overall, but sorting the distinct-group values is already efficient and simple for the given constraints.
| Time | O(n + k log k) | O(n) to build the map, O(k log k) to sort top values where k is # distinct x |
| Space | O(k) | Storing max y for each unique x in a hash map |

The dominant cost is sorting the maximum values of distinct `x`. For n up to 10^5, this is efficient since k ≤ n.

## Test Cases

```sql
sol = Solution()

assert sol.maxSumDistinctTriplet(
    [1, 2, 1, 3, 2],
    [5, 3, 4, 6, 2]
) == 14  # provided example

assert sol.maxSumDistinctTriplet(
    [1, 2, 1, 2],
    [4, 5, 6, 7]
) == -1  # fewer than three distinct x values

assert sol.maxSumDistinctTriplet(
    [1, 2, 3],
    [10, 20, 30]
) == 60  # exactly three distinct groups

assert sol.maxSumDistinctTriplet(
    [1, 1, 2, 2, 3, 3],
    [5, 10, 7, 1, 8, 4]
) == 25  # choose maxima from each group

assert sol.maxSumDistinctTriplet(
    [1, 2, 3, 4],
    [1, 2, 3, 4]
) == 9  # choose top three group values

assert sol.maxSumDistinctTriplet(
    [1, 1, 1, 2, 3],
    [1, 100, 50, 10, 20]
) == 130  # duplicate group with large maximum

assert sol.maxSumDistinctTriplet(
    [5, 5, 5],
    [1, 2, 3]
) == -1  # only one distinct x

assert sol.maxSumDistinctTriplet(
    [1, 2, 3, 4, 5],
    [1000000, 999999, 999998, 1, 1]
) == 2999997  # large values

assert sol.maxSumDistinctTriplet(
    [1, 2, 3, 4, 5, 6],
    [1, 10, 100, 1000, 10000, 100000]
) == 111000  # top three groups

Test Summary

Test	Why
Example 1	Validates the sample answer
Example 2	Validates impossible case
Exactly three groups	Smallest valid configuration
Duplicate groups	Ensures maximum per group is chosen
Four distinct groups	Ensures top three are selected
Heavy duplication	Tests replacement of group maxima
Single distinct value	Extreme invalid case
Large values	Verifies handling of upper bounds
Many distinct groups	Ensures correct top-three selection

Edge Cases

Fewer Than Three Distinct X Values

A common mistake is to count indices rather than distinct x values. For example:

x = [1,1,1,2,2]

Although there are five indices, there are only two distinct x values. No valid triplet exists. The implementation handles this by checking len(best_y) < 3 after grouping.

Multiple Occurrences of the Same X Value

Consider:

x = [1,1,1]
y = [5,10,20]

Only one occurrence can ever be chosen because all entries share the same x. The algorithm keeps only the maximum value, 20, ensuring the group is represented optimally.

Largest Y Values Belong to Duplicate Groups

Consider:

x = [1,1,2,3]
y = [100,90,5,6]

A naive solution that simply takes the three largest y values would choose 100, 90, and 6, which is invalid because the first two correspond to the same x.

The grouping step prevents this mistake by reducing the data to:

1 -> 100
2 -> 5
3 -> 6

The final answer becomes 111, which respects the distinctness requirement.

Exactly Three Distinct X Values

When there are exactly three distinct groups, every group must be used. For example:

x = [1,2,3]
y = [10,20,30]

After grouping, there are exactly three representatives, and their sum is returned directly. The implementation naturally handles this without any special logic.

test cases

assert Solution().maxSumDistinctTriplet([1,2,1,3,2], [5,3,4,6,2]) == 14 # Example 1 assert Solution().maxSumDistinctTriplet([1,2,1,2], [4,5,6,7]) == -1 # Example 2 assert Solution().maxSumDistinctTriplet([1,2,3], [1,2,3]) == 6 # Exactly 3 distinct x assert Solution().maxSumDistinctTriplet([1,1,1], [5,6,7]) == -1 # Only 1 distinct x assert Solution().maxSumDistinctTriplet([1,2,3,4], [10,20,30,40]) == 90 # More than 3 distinct x assert Solution().maxSumDistinctTriplet([5,5,5,10,10,15], [1,2,3,4,5,6]) == 14 # max from distinct x

| Test | Why |
| --- | --- |
| [1,2,1,3,2], [5,3,4,6,2] | Standard case with duplicates |
| [1,2,1,2], [4,5,6,7] | Fewer than 3 distinct x |
| [1,2,3], [1,2,3] | Exactly 3 distinct x |
| [1,1,1], [5,6,7] | Only 1 distinct x, impossible |
| [1,2,3,4], [10,20,30,40] | More than 3 distinct x, pick top 3 |
| [5,5,5,10,10,15], [1,2,3,4,5,6] | Ensures correct max_y selection per x |

## Edge Cases

One important edge case is when there are fewer than three distinct `x` values. A naive implementation might attempt to sum the first three elements without checking for distinctness. The algorithm explicitly checks `len(max_y_for_x) < 3` to handle this correctly.

Another edge case is when multiple entries share the same `x` value but have different `y` values.