Merge Triplets to Form Target Triplet

A triplet is an array of three integers. You are given a 2D array triplets and a triplet target. One operation picks two triplets i and j and replaces triplets[j] with their position-wise maximum: [max(ai, aj), max(bi, bj), max(ci, cj)]. You may apply it any number of times. Return true if target can appear as one of the triplets.

The limits are 1 <= triplets.length <= 10^5, triplets[i].length == target.length == 3, and every value is between 1 and 1000. This is LeetCode 1899.

Example 1
Input: triplets = [[2, 5, 3], [1, 8, 4], [1, 7, 5]], target = [2, 7, 5]
Output: true
Explanation: merging [2, 5, 3] with [1, 7, 5] gives [2, 7, 5].
Example 2
Input: triplets = [[3, 4, 5], [4, 5, 6]], target = [3, 2, 5]
Output: false
Explanation: no triplet has 2 or less in the middle, so the middle value can never be 2.
Example 3
Input: triplets = [[2, 5, 3], [2, 3, 4], [1, 2, 5], [5, 2, 3]], target = [5, 5, 5]
Output: true
Explanation: [2, 5, 3], [1, 2, 5] and [5, 2, 3] merge into [5, 5, 5].

How to Think About It

Step 1: What a chain of merges produces

Each merge takes a maximum per position, and taking a maximum is order free. So any sequence of merges ends with the position-wise maximum of some group of the original triplets. The question becomes: is there a group whose maximum is exactly target?

Step 2: Brute force

Trying every group means 2^n subsets, which is hopeless for 10^5 triplets. A simple rule decides which triplets may join the group.

Step 3: Some triplets can never be used

A maximum never goes down. If a triplet has any value larger than the target at the same position, putting it in the group makes that position too big for good. Such a triplet is poison, so skip it.

Step 4: Every safe triplet is free to use

A triplet with every value at most the target cannot hurt: its values are covered by the target anyway. So the best group is simply all safe triplets together. Their maximum is at most the target at every position, and it equals the target at position k exactly when some safe triplet has target[k] there.

Step 5: The greedy check

Scan once, skip poison triplets, and mark each position where a safe triplet hits the target value. The answer is true when all three positions are marked. This is a greedy choice in its purest form: take everything that cannot hurt.

Walkthrough

Example 1, target = [2, 7, 5]. The middle triplet is skipped because its 8 is above the target's 7.

TripletSafe?Positions that hit the targetmatched after
[2, 5, 3]yes0 (the 2)[true, false, false]
[1, 8, 4]no, 8 > 7skipped[true, false, false]
[1, 7, 5]yes1 (the 7) and 2 (the 5)[true, true, true]

All three positions are matched, so the answer is true.

Java Solution

The method makes one pass, ignores any triplet that exceeds the target somewhere, and records which target values the remaining triplets reach.

  • The filter: the continue runs when any of the three values is above the target. One bad value is enough, because merging can only raise it.
  • The marks: matched[k] becomes true when a safe triplet has exactly target[k] at position k. One triplet may set several marks at once, as [1, 7, 5] does in the walkthrough.
  • No merging needed: the code never builds the merged triplet. The marks are enough, since the safe triplets' maximum can only equal or fall below the target.
  • Edge cases: a single triplet equal to the target returns true with no merges at all. If every triplet is unsafe, no mark is set and the answer is false.

A common mistake is to mark positions without the filter. For triplets = [[2, 5, 9], [1, 1, 5]] and target = [2, 5, 5] that version returns true. The correct answer is false, because the 9 ruins any group that contains the triplet giving the 2 and the 5.

Java
public class MergeTripletsToFormTargetTriplet {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean[] matched = new boolean[3]; // matched[k]: a usable triplet has target[k] at k
        for (int[] t : triplets) {
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {
                continue; // merging this one would push a value past the target for good
            }
            for (int k = 0; k < 3; k++) {
                if (t[k] == target[k]) {
                    matched[k] = true;
                }
            }
        }
        return matched[0] && matched[1] && matched[2];
    }
}

Complexity

  • Time: O(n), where n is the number of triplets. Each triplet is looked at once, with at most three comparisons for the filter and three for the marks.
  • Space: O(1). The only extra memory is the fixed array of three booleans and the loop variables, no matter how many triplets the input holds.

The check matched a brute force that tries every subset on 100,000 random inputs with up to 10 triplets. Another greedy scan that keeps one running fact per step is Jump Game.