Merge Triplets to Form Target Triplet

Difficulty: Medium

You have a list of triplets, where each triplet is 3 numbers [x, y, z], and you're given one target triplet. You can pick any subset of your triplets and merge them: merging combines triplets by taking the maximum of each position across all the triplets you picked (so merging [2, 5, 3] and [1, 7, 5] gives [2, 7, 5]).

Determine whether it's possible to choose some triplets (you can use as many or as few as you like, in any order) so that merging them produces exactly the target triplet.

Examples

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true

Merging [2,5,3] and [1,7,5] gives [max(2,1), max(5,7), max(3,5)] = [2,7,5], which matches the target.

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false

Every triplet has a value greater than 2 in the second position, so merging can never bring that position down to 2 - merging only ever raises or keeps values, never lowers them.

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true

Merging [2,5,3], [1,2,5], and [5,2,3] gives [max(2,1,5), max(5,2,2), max(3,5,3)] = [5,5,5].

Constraints

1 <= triplets.length <= 10^5
triplets[i].length == target.length == 3
1 <= triplets[i][j], target[j] <= 1000

Approach

Since merging only takes maximums, it can never lower a value - so any triplet with a position that exceeds the target in that same position is immediately disqualified, because using it would push that position above the target with no way to bring it back down.

That means the greedy filter is simple: discard every triplet that overshoots the target anywhere. Among the triplets that remain (every value in every position is <= the target), check whether, for each of the 3 positions, at least one surviving triplet actually hits the target's value there. If all 3 positions are covered, merging all the surviving triplets together reproduces the target.

Solutions

Brute Force - Try Every Subset

Try every possible subset of triplets, merge each subset, and check if any subset's merge equals the target.

function mergeTriplets(triplets, target) {
  const n = triplets.length;
  for (let mask = 1; mask < (1 << n); mask++) {
    let merged = [0, 0, 0];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        for (let j = 0; j < 3; j++) {
          merged[j] = Math.max(merged[j], triplets[i][j]);
        }
      }
    }
    if (merged[0] === target[0] && merged[1] === target[1] && merged[2] === target[2]) {
      return true;
    }
  }
  return false;
}

Time: O(2^n * n) - every subset of n triplets, each taking O(n) to merge · Space: O(1)

Optimal - Filter Then Check Coverage

Discard any triplet that overshoots the target in some position, since merging can never lower a value. Then check whether each target position is matched by at least one surviving triplet.

function mergeTriplets(triplets, target) {
  const achieved = [false, false, false];

  for (const triplet of triplets) {
    if (triplet[0] > target[0] || triplet[1] > target[1] || triplet[2] > target[2]) {
      continue;
    }
    for (let j = 0; j < 3; j++) {
      if (triplet[j] === target[j]) achieved[j] = true;
    }
  }

  return achieved[0] && achieved[1] && achieved[2];
}

Time: O(n) · Space: O(1)