loading

Merge Triplets to Form Target Triplet — Step-by-Step Visualization

mediumLeetCode #1899ArrayGreedy

A triplet is an array of three integers. You are given a 2D integer array `triplets` and a 1D integer array `target`. To obtain `target`, you may apply merge operations on `triplets`: pick two triplets and replace one with `[max(a1,a2), max(b1,b2), max(c1,c2)]`. Return `true` if it is possible to obtain `target` as an element of `triplets` after any number of merge operations.

Algorithm Pattern

Greedy (Component-wise Max)

Key Idea

Only use triplets where no component exceeds the corresponding target value — using an over-limit triplet could corrupt a target component. Take the component-wise max of valid triplets.

Step-by-Step Approach

  1. Initialize res = [0, 0, 0].
  2. For each triplet t:
  3. If t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]:
  4. res = [max(res[0], t[0]), max(res[1], t[1]), max(res[2], t[2])].
  5. Return res == target.

Common Gotchas

  • A triplet with any component > target is useless — merging it would exceed target.
  • The order of merging doesn't matter because max is commutative and associative.

Related Problems

← All problems