Watch 9 video solutions for Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values, a medium level problem involving Array, Hash Table, Greedy. This walkthrough by Rapid Syntax has 312 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
i = 0 (x[i] = 1, y[i] = 5), j = 1 (x[j] = 2, y[j] = 3), k = 3 (x[k] = 3, y[k] = 6).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:
x. Hence, the output is -1.
Constraints:
n == x.length == y.length3 <= n <= 1051 <= x[i], y[i] <= 106Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplets | O(n^3) | O(1) | Small inputs or initial reasoning during interviews |
| Hash Table + Sorting | O(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 |