Skip to main content
Talentd

Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values - Solution & Explanation

MediumArrayHash TableGreedySorting9 min readAsked at: Amazon
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given pairs of (x, y). The goal is to pick exactly three elements such that their x values are all different and the total y sum is maximized. The challenge is enforcing the distinct x constraint while still selecting the three largest possible y values.

Approach 1: Brute Force Triplets (O(n^3) time, O(1) space)

Check every combination of three indices using three nested loops. For each triplet, verify that the three x values are distinct and compute the sum of their y values. Track the maximum valid sum found. This method directly models the problem but becomes impractical for large inputs because the number of triplets grows cubically.

Approach 2: Hash Table + Sorting (O(n log n) time, O(n) space)

Only one element per x can appear in the final triplet. That means for each distinct x, you only care about the maximum y. Use a hash table to map each x to the largest y seen while iterating through the input. After building this map, collect the values and sort them in descending order using sorting. The answer is the sum of the top three values if at least three unique x exist. This reduces the search space from n elements to the number of unique x values.

Approach 3: Hash Table + Min Heap (O(n log k) time, O(n) space)

The map-building step remains the same: iterate once and store the best y for every x. Instead of sorting all values, maintain a size‑3 min heap using a heap (priority queue). Push each candidate y into the heap and remove the smallest whenever the heap grows beyond three elements. After processing all values, the heap contains the three largest y values from distinct x keys. This avoids sorting the entire list and keeps only the necessary candidates.

Recommended for interviews: Interviewers typically expect the hash table reduction followed by sorting or a small heap. Recognizing that each x contributes at most one useful candidate is the key greedy insight. Mentioning the brute force approach shows baseline reasoning, but implementing the hash map + sorting or heap solution demonstrates strong optimization skills.

Solution

We pair the elements of arrays x and y into a 2D array arr, and then sort 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 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.

If we manage to select three different x values during the iteration, we return the sum of their corresponding y values; if we finish iterating without selecting three distinct x values, we return -1.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of arrays x and y.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force TripletsO(n^3)O(1)Small inputs or initial reasoning during interviews
Hash Table + SortingO(n log n)O(n)General solution when extracting top values after grouping by x
Hash Table + Min Heap (Top 3)O(n log 3) ≈ O(n)O(n)When only the top 3 values are needed and you want to avoid full sorting

Video Solution

3572. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values | Biweekly Contest 158 | Leetcode • Rapid Syntax • 316 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Maximize Y-Sum by Picking a Triplet of Distinct X-Values easy or hard?
The problem is generally rated Medium because the brute force idea is simple but inefficient. Recognizing that only the best y per x matters and then selecting the top three values requires a combination of greedy thinking and efficient data structures.
Maximize Y-Sum by Picking a Triplet of Distinct X-Values Python/Java solution
Most implementations first build a dictionary or map where each x stores the largest y seen. After that, either sort the values and sum the top three or use a priority queue of size three. This approach works consistently across Python, Java, C++, Go, and TypeScript.
How to solve Maximize Y-Sum by Picking a Triplet of Distinct X-Values in O(n)?
First iterate through the array and use a hash map to keep the maximum y for each x. Then push those values into a min heap of size 3, removing the smallest whenever the heap exceeds three elements. This keeps only the three largest y values from distinct x keys and runs in O(n log 3) ≈ O(n).
What is the best approach for Maximize Y-Sum by Picking a Triplet of Distinct X-Values?
The most practical solution uses a hash table to store the maximum y value for each distinct x, then selects the top three values. This can be done by sorting the values (O(n log n)) or maintaining a min heap of size 3 (O(n log 3)). The key insight is that each x can contribute only one candidate to the final triplet.
Is Maximize Y-Sum by Picking a Triplet of Distinct X-Values asked at Google/Amazon/Meta?
Problems combining hash tables, greedy selection, and top-k elements frequently appear in interviews at companies like Amazon and Google. Variants involving grouping by key and selecting maximum values are common in coding rounds and online assessments.
What data structure is used in Maximize Y-Sum by Picking a Triplet of Distinct X-Values?
The core data structures are a hash table for grouping values by x and either sorting or a min heap (priority queue) to extract the top three y values. These structures enforce the distinct-x constraint while efficiently identifying the best candidates.
What is the time complexity of Maximize Y-Sum by Picking a Triplet of Distinct X-Values?
The optimal approach runs in O(n log n) time when sorting the candidate values after building a hash map of best y per x. Using a fixed-size heap reduces the selection step to O(n log 3), which is effectively O(n). Space complexity is O(n) for storing the x to max-y mapping.

Ready to solve this problem?

Practice Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values with our built-in code editor and test cases.

Practice on FleetCode
Previous

Largest Values From Labels

Next

Maximum Sum of 3 Non-Overlapping Subarrays