⚡Flashcard Drill➔
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

  1. Only the largest y for each distinct x can ever be useful, so reduce the data to one value per x.
  2. Build a map from x to the maximum y seen for that x.
  3. If fewer than three distinct x values exist, no valid triplet exists -- return -1.
  4. Otherwise sort the per-x maxima 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 y values without deduplicating x: two of them may share an x value and violate the distinctness rule.
  • Returning -1 without checking the distinct count: fewer than three distinct x values means the triplet is impossible.
  • Keeping the smallest y per x: only the maximum per x can help maximise the sum.
  • Assuming the three chosen indices must be sorted: only their x values 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems