Neetcode 150 - Merge Triplets to Form Target

1. Input, Output, Contraints

Input:

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

Output:

True

We can merge: [2,5,3], [1,7,5]

=> Merging → [max(2,1), max(5,7), max(3,5)] = [2,7,5] ✅ equals target.

Contraints:

1 ≤ len(triplets) ≤ 10^5
Each element ≤ 1000

2. Dry run

Triplet	Compare to target	Keep it?
[2,5,3]	≤ [2,7,5] ✅	Yes
[1,8,4]	8 > 7 ❌	No
[1,7,5]	≤ [2,7,5] ✅	Yes

=> Find the target reach maximum of current pairs.

3. Naive Solution

def mergeTriplets_naive(triplets, target):
    n = len(triplets)
    for i in range(n):
        for j in range(i + 1, n):
            merged = [
                max(triplets[i][0], triplets[j][0]),
                max(triplets[i][1], triplets[j][1]),
                max(triplets[i][2], triplets[j][2]),
            ]
            if merged == target:
                return True
    return False

⏱️ Complexity:

Time Complexity: O(N^2).
Space Complexity: O(1)

4. Optimized Solution

def mergeTriplets(triplets, target):
    x = y = z = False
    tx, ty, tz = target

    for a, b, c in triplets:
        # Step 1: skip invalid triplet
        if a > tx or b > ty or c > tz:
            continue

        # Step 2: mark matching positions
        if a == tx: x = True
        if b == ty: y = True
        if c == tz: z = True

    # Step 3: all positions achieved
    return x and y and z

⏱️ Complexity:

Time Complexity: O(N).
Space Complexity: O(1)

Last Updated On October 17, 2025