⚡Flashcard Drill➔
NeetCode #793LC-1899MediumGreedyNC 150NC 250
← Back to All Problems

#793 · #1899 · Merge Triplets to Form Target Triplet(合并若干三元组以形成目标三元组)

📌 Problem Statement & Constraints

You are given a 2D array triplets and an integer array target. In one operation pick two triplets and replace them with their element-wise maximum. Return true if you can obtain target. Constraints: 1 <= triplets.length <= 10^5, triplets[i].length == 3, 1 <= triplets[i][j], target[j] <= 1000.

💡 Core Algorithmic Approaches

  1. Any triplet with an element strictly greater than the corresponding target element can never be used, because the element-wise max is monotone and can never decrease.
  2. Discard those triplets, then ask whether each target position can be matched by some surviving triplet.
  3. A surviving triplet contributes its value only where it equals the target, since maxing can only raise values up to the target.
  4. If all three positions are matched, merge those triplets to form the target.

💻 Benchmark Python3 Implementation

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        found = [False, False, False]
        for t in triplets:
            if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
                continue               # cannot be part of the max
            for i in range(3):
                if t[i] == target[i]:
                    found[i] = True
        return all(found)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the triplets.
💾 Space Complexity
O(1): a three-element flag list.

⚠️ Interview Pitfalls & Follow-ups

  • Keeping a triplet that overshoots the target in one coordinate: maxing it in would make that coordinate exceed the target permanently.
  • Requiring one single triplet to equal the target: the answer may be assembled from three different triplets.
  • Forgetting that max never decreases a coordinate: this is exactly why overshooting triplets are unusable.
  • Comparing against the running merged triplet rather than the target: the target is the fixed reference.
⚡
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