Sweaty Imposter

Merge Triplets to Form Target Triplet

MediumGreedyNeetCode 150MidOpen on LeetCodeUpdated

You're given a list of triplets, each [a, b, c], and a target triplet [x, y, z]. One operation picks two triplets i and j and replaces triplet j with [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)]. Return true if some sequence of operations, possibly empty, can make target appear as an element of triplets, and false otherwise.

Examples

triplets = [[1,4,2],[3,1,5],[2,4,1]], target = [3,4,5] returns true

Merging [1,4,2] with [3,1,5] gives [3,4,5].

triplets = [[2,6,3],[4,2,1]], target = [4,5,3] returns false

Any merge that includes [2,6,3] pushes the middle value past 5, and [4,2,1] alone never reaches 5 in the middle.

triplets = [[5,5,5]], target = [5,5,5] returns true

The target is already in the list, and zero operations are allowed.

Constraints

  • 1 <= triplets.length <= 10^5
  • triplets[i].length == target.length == 3
  • 1 <= a, b, c, x, y, z <= 1000

Hints

Hint 1

max never decreases a value. What does that mean for a triplet with a value larger than the target's in the same position?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

A merge only ever raises values, so a triplet with any value above the target's in the same position can never take part: skip it. Every other triplet is safe to merge in, because it can't push anything past the target. That leaves one question: does each of the three positions have a safe triplet that matches the target exactly there? Scan once with three flags. O(n) time and O(1) space.

Time

O(n)

Space

O(1)

Pitfall

Looking for a single triplet equal to the target, or merging every triplet. The three target values can come from different triplets, and one triplet that overshoots any position spoils every merge it joins.

Solutions

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean[] found = new boolean[3];
        for (int[] t : triplets) {
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;
            for (int i = 0; i < 3; i++) {
                if (t[i] == target[i]) found[i] = true;
            }
        }
        return found[0] && found[1] && found[2];
    }
}
Drill This