367. Merge Triplets to Form Target Triplet

Since merging only takes maximums, a triplet that exceeds the target in any position can never be used (it would overshoot). Among the safe triplets, we just need each target position to be matched exactly by at least one.

Key observation

The merge operation takes element-wise maximums, so a value can only grow. Therefore:

• A triplet with any component greater than the target is useless — using it would push that position above the target forever.
• Among the remaining 'safe' triplets (all components ≤ target), we only need each of the three positions to be hit exactly by some triplet.

Collect the set of positions where a safe triplet equals the target. If all three positions {0,1,2} are covered, merging those triplets reproduces the target.

Walk-through

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

• [2,5,3] safe, matches position 0 (2). [1,8,4] has 8 > 7 → skip. [1,7,5] safe, matches positions 1 (7) and 2 (5).
• Covered {0,1,2} → true.

Complexity

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

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        Set<Integer> good = new HashSet<>();
        for (int[] t : triplets) {
            if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
                for (int i = 0; i < 3; i++) {
                    if (t[i] == target[i]) good.add(i);
                }
            }
        }
        return good.size() == 3;
    }
}