NeetCode #787LC-3572MediumGreedy
← Back to All Problems#787 · #3572 · Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values(最大化 X 值三元组的 Y 值和)
📌 Problem Statement & Constraints
You are given two integer arrays
x and y of the same length n. Choose three indices i, j, k with distinct x values so that y[i] + y[j] + y[k] is maximised. Return that maximum sum, or -1 if it is impossible. Constraints: 3 <= n <= 10^5, 1 <= x[i], y[i] <= 10^9.💡 Core Algorithmic Approaches
- Only the largest
yfor each distinctxcan ever be useful, so reduce the data to one value perx. - Build a map from
xto the maximumyseen for thatx. - If fewer than three distinct
xvalues exist, no valid triplet exists -- return -1. - Otherwise sort the per-
xmaxima descending and sum the top three.
💻 Benchmark Python3 Implementation
class Solution:
def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
best = {}
for xi, yi in zip(x, y):
if yi > best.get(xi, -1):
best[xi] = yi # keep the largest y per distinct x
if len(best) < 3:
return -1
top = sorted(best.values(), reverse=True)[:3]
return sum(top)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): building the map is O(n), sorting the distinct values dominates.
💾 Space Complexity
O(n): the map of per-x maxima.
⚠️ Interview Pitfalls & Follow-ups
- Picking the top three
yvalues without deduplicatingx: two of them may share anxvalue and violate the distinctness rule. - Returning -1 without checking the distinct count: fewer than three distinct
xvalues means the triplet is impossible. - Keeping the smallest
yperx: only the maximum perxcan help maximise the sum. - Assuming the three chosen indices must be sorted: only their
xvalues must be distinct.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.