1899. Merge Triplets to Form Target Triplet (Medium)

Problem

Given a list of triplets and a target triplet, you may pick a subset and take element-wise max to produce a new triplet. Return true if you can produce exactly target.

Example

• triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] → true ([2,5,3] + [1,7,5])
• triplets = [[1,3,4],[2,5,8]], target = [2,5,8] → true
• triplets = [[3,4,5]], target = [2,5,8] → false

LeetCode 1899 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, enumerate subsets

Check the element-wise max of every subset.

Python

from itertools import combinations

def merge_triplets(triplets, target):
    n = len(triplets)
    for r in range(1, n + 1):                              # L1: every subset size
        for subset in combinations(triplets, r):           # L2: 2^n total subsets
            mx = [0, 0, 0]
            for t in subset:
                for i in range(3):
                    if t[i] > mx[i]:
                        mx[i] = t[i]
            if mx == list(target):
                return True
    return False

TypeScript

function mergeTriplets(triplets: number[][], target: number[]): boolean {
    const n = triplets.length;
    function* subsets(r: number, start: number): Generator<number[][]> {
        if (r === 0) { yield []; return; }
        for (let i = start; i <= n - r; i++) {
            for (const rest of subsets(r - 1, i + 1)) {
                yield [triplets[i], ...rest];
            }
        }
    }
    for (let r = 1; r <= n; r++) {                         // L1: every subset size
        for (const subset of subsets(r, 0)) {              // L2: 2^n total subsets
            const mx = [0, 0, 0];
            for (const t of subset) {
                for (let i = 0; i < 3; i++) {
                    if (t[i] > mx[i]) mx[i] = t[i];
                }
            }
            if (mx[0] === target[0] && mx[1] === target[1] && mx[2] === target[2]) return true;
        }
    }
    return false;
}

Go

func mergeTriplets(triplets [][]int, target []int) bool {
    n := len(triplets)
    var comb func(start, r int, chosen [][]int) bool
    comb = func(start, r int, chosen [][]int) bool {
        if r == 0 {
            mx := [3]int{}
            for _, t := range chosen {                     // L2: 2^n total subsets
                for i := 0; i < 3; i++ {
                    if t[i] > mx[i] { mx[i] = t[i] }
                }
            }
            return mx[0] == target[0] && mx[1] == target[1] && mx[2] == target[2]
        }
        for i := start; i <= n-r; i++ {                   // L1: every subset size
            if comb(i+1, r-1, append(chosen, triplets[i])) { return true }
        }
        return false
    }
    for r := 1; r <= n; r++ {
        if comb(0, r, nil) { return true }
    }
    return false
}

Swift

final class Solution {
    func mergeTriplets(_ triplets: [[Int]], _ target: [Int]) -> Bool {
        for mask in 1..<(1 << triplets.count) {
            var merged = [0, 0, 0]
            for index in triplets.indices where mask & (1 << index) != 0 {
                for channel in 0..<3 { merged[channel] = max(merged[channel], triplets[index][channel]) }
            }
            if merged == target { return true }
        }
        return false
    }
}

There are 2^n subsets; each costs $O(n)$ to combine. Total $O(n · 2^n)$. Skip past tiny inputs.

Complexity

• Time: $O(n · 2^n)$.
• Space: $O(n)$.

Approach 2: Greedy channel-wise (canonical)

A triplet (a, b, c) is “usable” iff every channel is ≤ target. If any channel exceeds target, including it pushes that channel past the answer and can’t be undone.

Among usable triplets, check that each of the three channels gets at least one triplet achieving that target channel.

Python

def merge_triplets(triplets, target):
    hit = [False, False, False]                         # L1: O(1)
    for t in triplets:                                  # L2: single pass, n iterations
        if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:  # L3: O(1)
            continue
        for i in range(3):                              # L4: O(1), constant 3 channels
            if t[i] == target[i]:
                hit[i] = True                           # L5: O(1)
    return all(hit)                                     # L6: O(1)

TypeScript

function mergeTriplets(triplets: number[][], target: number[]): boolean {
    const hit = [false, false, false];                             // L1: O(1)
    for (const t of triplets) {                                    // L2: single pass, n iterations
        if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;  // L3: O(1)
        for (let i = 0; i < 3; i++) {                             // L4: O(1), constant 3 channels
            if (t[i] === target[i]) hit[i] = true;                // L5: O(1)
        }
    }
    return hit[0] && hit[1] && hit[2];                            // L6: O(1)
}

Go

func mergeTriplets(triplets [][]int, target []int) bool {
    hit := [3]bool{}                                               // L1: O(1)
    for _, t := range triplets {                                   // L2: single pass, n iterations
        if t[0] > target[0] || t[1] > target[1] || t[2] > target[2] { continue } // L3: O(1)
        for i := 0; i < 3; i++ {                                  // L4: O(1), constant 3 channels
            if t[i] == target[i] { hit[i] = true }                // L5: O(1)
        }
    }
    return hit[0] && hit[1] && hit[2]                             // L6: O(1)
}

Swift

final class Solution {
    func mergeTriplets(_ triplets: [[Int]], _ target: [Int]) -> Bool {
        var matched = [false, false, false]
        for triplet in triplets where zip(triplet, target).allSatisfy({ $0 <= $1 }) {
            for channel in 0..<3 where triplet[channel] == target[channel] { matched[channel] = true }
        }
        return matched.allSatisfy { $0 }
    }
}

Where the time goes, line by line

Variables: n = len(triplets).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2, L3, L4, L5 (scan)	$O(1)$	n	$O(n)$ ← dominates
L6 (all check)	$O(1)$	1	$O(1)$

Each triplet is visited once; the inner channel loop is constant (always 3 channels).

Complexity

• Time: $O(n)$, driven by L2/L3/L4/L5 (single pass over all triplets).
• Space: $O(1)$.

Why greedy works

Element-wise max is monotone, once a channel equals the target, subsequent usable triplets can’t reduce it below target. So we just need one usable triplet per channel hitting the target value.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Early-exit variant

Same as Approach 2 with an early return when all three hits are set.

Python

def merge_triplets_early(triplets, target):
    hit = 0                                             # L1: O(1), bitmask
    for t in triplets:                                  # L2: single pass, n iterations
        if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:  # L3: O(1)
            continue
        for i in range(3):                              # L4: O(1)
            if t[i] == target[i]:
                hit |= 1 << i                           # L5: O(1)
        if hit == 0b111:                                # L6: O(1) early exit
            return True
    return hit == 0b111

TypeScript

function mergeTripletsEarly(triplets: number[][], target: number[]): boolean {
    let hit = 0;                                                   // L1: O(1), bitmask
    for (const t of triplets) {                                    // L2: single pass, n iterations
        if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;  // L3: O(1)
        for (let i = 0; i < 3; i++) {                             // L4: O(1)
            if (t[i] === target[i]) hit |= 1 << i;                // L5: O(1)
        }
        if (hit === 0b111) return true;                            // L6: O(1) early exit
    }
    return hit === 0b111;
}

Go

func mergeTripletsEarly(triplets [][]int, target []int) bool {
    hit := 0                                                       // L1: O(1), bitmask
    for _, t := range triplets {                                   // L2: single pass, n iterations
        if t[0] > target[0] || t[1] > target[1] || t[2] > target[2] { continue } // L3: O(1)
        for i := 0; i < 3; i++ {                                  // L4: O(1)
            if t[i] == target[i] { hit |= 1 << i }                // L5: O(1)
        }
        if hit == 0b111 { return true }                            // L6: O(1) early exit
    }
    return hit == 0b111
}

Swift

final class Solution {
    func mergeTriplets(_ triplets: [[Int]], _ target: [Int]) -> Bool {
        var mask = 0
        for triplet in triplets {
            if zip(triplet, target).contains(where: { $0 > $1 }) { continue }
            for channel in 0..<3 where triplet[channel] == target[channel] { mask |= 1 << channel }
            if mask == 0b111 { return true }
        }
        return false
    }
}

Where the time goes, line by line

Variables: n = len(triplets).

Line	Per-call cost	Times executed	Contribution
L2-L5 (scan)	$O(1)$	up to n	$O(n)$ ← dominates
L6 (early exit check)	$O(1)$	up to n	$O(n)$

Same asymptotic complexity as Approach 2 with a constant-factor speedup on lucky inputs where all three channels are hit early.

Complexity

• Same as Approach 2 with constant-factor speedup on lucky inputs.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Enumerate subsets	exponential	$O(n)$
Greedy channel-wise	$O(n)$	$O(1)$

The “filter then hit each dimension” greedy pattern generalizes to K channels.

Test cases

Go

func mergeTriplets(triplets [][]int, target []int) bool {
    hit := [3]bool{}
    for _, t := range triplets {
        if t[0] > target[0] || t[1] > target[1] || t[2] > target[2] { continue }
        for i := 0; i < 3; i++ {
            if t[i] == target[i] { hit[i] = true }
        }
    }
    return hit[0] && hit[1] && hit[2]
}

Python

# Quick smoke tests, paste into a REPL or save as test_1899.py and run.
# Uses the canonical implementation (Approach 2: greedy channel-wise).

def merge_triplets(triplets, target):
    hit = [False, False, False]
    for t in triplets:
        if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
            continue
        for i in range(3):
            if t[i] == target[i]:
                hit[i] = True
    return all(hit)

def _run_tests():
    assert merge_triplets([[2,5,3],[1,8,4],[1,7,5]], [2,7,5]) == True
    assert merge_triplets([[1,3,4],[2,5,8]], [2,5,8]) == True
    assert merge_triplets([[3,4,5]], [2,5,8]) == False    # overshoots channel 0
    assert merge_triplets([[1,1,1]], [1,1,1]) == True     # single triplet matches target
    assert merge_triplets([[1,0,0],[0,1,0],[0,0,1]], [1,1,1]) == True  # each channel from different triplet
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function mergeTriplets(triplets: number[][], target: number[]): boolean {
    const hit = [false, false, false];
    for (const t of triplets) {
        if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;
        for (let i = 0; i < 3; i++) {
            if (t[i] === target[i]) hit[i] = true;
        }
    }
    return hit[0] && hit[1] && hit[2];
}

console.assert(mergeTriplets([[2,5,3],[1,8,4],[1,7,5]], [2,7,5]) === true);
console.assert(mergeTriplets([[1,3,4],[2,5,8]], [2,5,8]) === true);
console.assert(mergeTriplets([[3,4,5]], [2,5,8]) === false);    // overshoots channel 0
console.assert(mergeTriplets([[1,1,1]], [1,1,1]) === true);     // single triplet matches target
console.assert(mergeTriplets([[1,0,0],[0,1,0],[0,0,1]], [1,1,1]) === true);
console.log("all tests pass");

Related data structures

• Arrays, channel-wise scan

Related concepts

• Greedy Algorithms, the local choice pattern protected by an invariant about the best reachable future.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.