#3572

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

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

Select three distinct x-values from arrays to maximize the sum of their corresponding y-values efficiently using hashing and sorting.

array hash table greedy sorting heap priority queue

Problem Statement

Given two integer arrays x and y of length n, choose three distinct indices i, j, k such that x[i], x[j], and x[k] are all different. Your task is to maximize y[i] + y[j] + y[k] among all valid triplets.

Return the maximum sum achievable under these conditions. If it is impossible to pick three distinct x-values, return -1. Focus on using array scanning with hash lookup to identify the top y-values for each unique x efficiently.

Examples

Example 1

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

Output: 14

Example 2

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

Output: -1

Constraints

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

Solution Approach

Use Hash Map to Track Maximum y per x

Iterate over the arrays and store each x with its maximum y in a hash map. Ignore any smaller y-values for the same x to prevent redundant calculations.

Collect and Sort Maximum y-values

Extract all maximum y-values from the hash map and sort them in descending order. Sorting enables quick selection of the largest three y-values corresponding to distinct x-values.

Return Top Three Sum or -1

If there are at least three unique x-values, sum the top three y-values from the sorted list and return it. Otherwise, return -1 to indicate no valid triplet exists.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for building the hash map and O(k log k) for sorting k unique x-values, where k <= n. Space complexity is O(k) for storing maximum y-values for each unique x in the hash map.

What Interviewers Usually Probe

Ask for maximum sum with distinct x-values
Check if candidate ignores duplicate x-values when selecting y
Look for O(n) hash map preprocessing plus sorting for top three selection

Common Pitfalls or Variants

Common pitfalls

Including multiple y-values for the same x, leading to invalid triplets
Not handling fewer than three unique x-values, returning incorrect sum
Sorting all y-values instead of only the maximums, increasing unnecessary computation

Follow-up variants

Maximize sum with four distinct x-values instead of three
Select triplet under a threshold constraint on y-values
Minimize sum by picking distinct x-values instead of maximizing

FAQ

What is the main pattern used in Maximize Y-Sum by Picking a Triplet of Distinct X-Values?

The core pattern is array scanning combined with hash lookup to track the maximum y for each unique x.

How do I handle duplicates in x while maximizing the y-sum?

Keep only the maximum y for each unique x in a hash map and ignore smaller y-values for the same x.

What should I return if fewer than three distinct x-values exist?

Return -1 because no valid triplet can be formed.

Is sorting all y-values necessary for this problem?

No, only the maximum y-values for each unique x need to be sorted, reducing unnecessary computation.

Can this approach scale to large arrays?

Yes, using a hash map to track maximum y-values ensures O(n) preprocessing and O(k log k) sorting, suitable for n up to 105.

terminal

Solution

Solution 1: Sorting + Greedy + Hash Table

We pair the elements of arrays $x$ and $y$ into a 2D array $\textit{arr}$, and then sort $\textit{arr}$ in descending order by the value of $y$. Next, we use a hash table to record the $x$ values that have already been selected, and iterate through $\textit{arr}$, each time selecting an $x$ value and its corresponding $y$ value that has not been chosen yet, until we have selected three distinct $x$ values.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
        arr = [(a, b) for a, b in zip(x, y)]
        arr.sort(key=lambda x: -x[1])
        vis = set()
        ans = 0
        for a, b in arr:
            if a in vis:
                continue
            vis.add(a)
            ans += b
            if len(vis) == 3:
                return ans
        return -1

Continue Practicing

#2813 maximum elegance of a k length subsequence #3462 maximum sum with at most k elements #3362 zero array transformation iii