Merge Triplets to Form Target Triplet

Problem Description

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the target triplet you want to obtain.

To obtain target, you may apply the following operation on triplets any number of times (possibly zero):

• Choose two indices i and j (i != j) and update triplets[j] to be [max(ai, aj), max(bi, bj), max(ci, cj)].

Return true if it is possible to obtain the target triplet [x, y, z], or false otherwise.

Examples

Constraints

• 1 ≤ triplets.length ≤ 10⁵
• triplets[i].length == target.length == 3
• 1 ≤ ai, bi, ci, x, y, z ≤ 1000

Filter Out Unusable Triplets

The operation only allows us to take the maximum element at each position. This means that if any triplet has an element that is strictly greater than the corresponding element in target (i.e. a > x, b > y, or c > z), that triplet is completely unusable. If we were to merge it, that coordinate would exceed the target value and we could never decrease it back down.

We filter out these unusable triplets. For the remaining usable triplets, we simply check if we can form the target:

• Do we have at least one triplet with a == x?
• Do we have at least one triplet with b == y?
• Do we have at least one triplet with c == z?

If all three conditions are met, we can merge all of these valid triplets together to form exactly [x, y, z].

Solution: Greedy Filtering

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean foundX = false;
        boolean foundY = false;
        boolean foundZ = false;

        for (int[] t : triplets) {
            // skip triplets that exceed the target in any coordinate
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {
                continue;
            }

            if (t[0] == target[0]) foundX = true;
            if (t[1] == target[1]) foundY = true;
            if (t[2] == target[2]) foundZ = true;

            if (foundX && foundY && foundZ) return true; // early exit
        }

        return foundX && foundY && foundZ;
    }
}

class Solution:
    def mergeTriplets(self, triplets: list[list[int]], target: list[int]) -> bool:
        x, y, z = target
        found_x = found_y = found_z = False

        for a, b, c in triplets:
            # skip triplets that exceed target in any coordinate
            if a > x or b > y or c > z:
                continue

            if a == x:
                found_x = True
            if b == y:
                found_y = True
            if c == z:
                found_z = True

            if found_x and found_y and found_z:
                return True

        return found_x and found_y and found_z

#include <vector>

class Solution {
public:
    bool mergeTriplets(std::vector<std::vector<int>>& triplets, std::vector<int>& target) {
        bool foundX = false;
        bool foundY = false;
        bool foundZ = false;

        for (const auto& t : triplets) {
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {
                continue;
            }

            if (t[0] == target[0]) foundX = true;
            if (t[1] == target[1]) foundY = true;
            if (t[2] == target[2]) foundZ = true;

            if (foundX && foundY && foundZ) return true;
        }

        return foundX && foundY && foundZ;
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the number of triplets. We make a single pass over the array.
• Space Complexity: O(1) space.

← All Problems