Merge Triplets to Form Target Triplet

medium greedy array

Problem

You are given a list of triplets, each holding three integers [a, b, c], plus a target triplet [x, y, z]. In one operation you may pick any two triplets and overwrite one of them with their element-wise maximum: [max(a₁,a₂), max(b₁,b₂), max(c₁,c₂)]. You may repeat the operation as often as you like.

Return true if some sequence of operations can make the target triplet appear in the list, and false otherwise.

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

Outputtrue

Merging [2,5,3] with [1,7,5] gives [max(2,1), max(5,7), max(3,5)] = [2,7,5], which is exactly the target.

triplets (a,b,c separated by ;)

target (x,y,z)

def merge_triplets(triplets, target):
    best = [0, 0, 0]
    for a, b, c in triplets:
        if a <= target[0] and b <= target[1] and c <= target[2]:
            best[0] = max(best[0], a)
            best[1] = max(best[1], b)
            best[2] = max(best[2], c)
    return best == target

function mergeTriplets(triplets, target) {
  const best = [0, 0, 0];
  for (const [a, b, c] of triplets) {
    if (a <= target[0] && b <= target[1] && c <= target[2]) {
      best[0] = Math.max(best[0], a);
      best[1] = Math.max(best[1], b);
      best[2] = Math.max(best[2], c);
    }
  }
  return best[0] === target[0] && best[1] === target[1] && best[2] === target[2];
}

boolean mergeTriplets(int[][] triplets, int[] target) {
    int[] best = {0, 0, 0};
    for (int[] t : triplets) {
        if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
            best[0] = Math.max(best[0], t[0]);
            best[1] = Math.max(best[1], t[1]);
            best[2] = Math.max(best[2], t[2]);
        }
    }
    return Arrays.equals(best, target);
}

bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
    vector<int> best = {0, 0, 0};
    for (auto& t : triplets) {
        if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
            best[0] = max(best[0], t[0]);
            best[1] = max(best[1], t[1]);
            best[2] = max(best[2], t[2]);
        }
    }
    return best == target;
}

Explanation

The merge operation only takes maximums, so values can grow but never shrink. That single observation drives the whole greedy solution: if a triplet has even one value above the target in some coordinate, then any merge that touches it pushes that coordinate above the target forever. Such a triplet is poison — discard it.

Every surviving triplet sits at or below the target in all three coordinates. Merging survivors can therefore never overshoot, which means it is always safe — and always best — to merge all of them. The result of merging everything is simply the element-wise maximum best over the survivors.

So the question collapses to: does best equal target? Equivalently, for each coordinate k some survivor must hit target[k] exactly; the other two values of that survivor are ≤ the target anyway, so including it costs nothing.

Walking the default example with target = [2,7,5]: triplet [2,5,3] fits everywhere, so best = [2,5,3]. Triplet [1,8,4] has 8 > 7 in the middle coordinate — discarded. Triplet [1,7,5] fits, and merging gives best = [2,7,5]. That equals the target, so the answer is true.

The scan looks at each triplet once and keeps only three running maximums, so the time is O(n) and the extra space is O(1). No search over merge orders is needed because max is commutative and associative — the order of merges never matters.

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