Merge Triplets to Form Target Triplet

Concept

LeetCode #1899.
Problem: You are given a 2D array of triplets, where triplets[i] = [ai, bi, ci], and a 1D array target = [x, y, z]. You can apply the following operation any number of times: Choose two indices (i, j) and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)]. Return true if you can obtain the target triplet, or false otherwise.

triplets = [[2,5,3], [1,8,4], [1,7,5]], target = [2,7,5]

• Merge [2,5,3] and [1,7,5].
• Max of A: max(2, 1) = 2
• Max of B: max(5, 7) = 7
• Max of C: max(3, 5) = 5
• The result is [2,7,5]! Output: true.

The Greedy Strategy

The problem sounds like complex combinatorial logic, but the mathematical reality of the max() function makes it incredibly simple.

Because we exclusively use max(), numbers can only go up. They can never go down.
If we ever merge a triplet that contains a number larger than our target (e.g., Target is 7, and we merge an 8), our value becomes 8 permanently. We can never reduce it back to 7. Our triplet is permanently ruined.

The Greedy Rule:

1. Throw away any triplet that contains a number strictly larger than our target. They are poisonous.
2. Out of all the safe triplets remaining, just merge them all together!
3. If the final merged super-triplet exactly matches the target, return true.

Implementation

We don’t even need to physically merge the arrays. We just keep a running tally using three boolean flags: “Have we found the target X?”, “Have we found the target Y?”, “Have we found the target Z?”.

// Time Complexity: O(N) (One single pass)
// Space Complexity: O(1)

function mergeTriplets(triplets: number[][], target: number[]): boolean {
    const [targetA, targetB, targetC] = target;

    // Track if we have successfully found pieces of our target
    let foundA = false;
    let foundB = false;
    let foundC = false;

    for (const [a, b, c] of triplets) {
        
        // RULE 1: Is this triplet poisonous?
        // If ANY value exceeds the target, we must completely ignore it!
        if (a > targetA || b > targetB || c > targetC) {
            continue; 
        }

        // RULE 2: It's safe! Does it contain any pieces we need?
        if (a === targetA) foundA = true;
        if (b === targetB) foundB = true;
        if (c === targetC) foundC = true;

        // Early Exit Optimization: We found all three!
        if (foundA && foundB && foundC) {
            return true;
        }
    }

    // We finished scanning. Did we find all three pieces?
    return foundA && foundB && foundC;
}

Why it works

This is a quintessential Greedy problem because it relies heavily on the Greedy Choice Property.
We never simulate “what if we merge this, but not that?”
Because of the mathematical nature of max(), merging a safe triplet can never hurt us!
If a triplet is safe, it is always globally optimal to merge it into our pile, because it might provide a piece of the target we need, and it mathematically cannot push our values above the ceiling. We aggressively greedily consume all safe triplets.

Interview Questions

Q: A developer uses a dynamic array to simulate the physical merging process: currentMax = [Math.max(...), Math.max(...)]. Is this correct?
A: Yes, it will result in the correct answer, but it is suboptimal. Creating arrays and physically updating variables on every iteration incurs memory and CPU overhead. The boolean flag approach achieves the exact same mathematical conclusion using pure bit-level logic, making it significantly faster and perfectly optimized.

Q: What if the problem used min() instead of max()?
A: The logic simply inverses! Numbers can only go down. Any triplet containing a number smaller than the target becomes poisonous, because it permanently drags the minimum down below the target. You filter out all triplets with numbers smaller than the target, and merge the remaining safe ones to see if they successfully drive the minimums down to exactly match the target.