1899. Merge Triplets to Form Target Triplet - Explanation

Description

You are given a 2D array of integers triplets, where triplets[i] = [ai, bi, ci] represents the ith triplet. You are also given an array of integers target = [x, y, z] which is the triplet we want to obtain.

To obtain target, you may apply the following operation on triplets zero or more times:

Choose two different triplets triplets[i] and triplets[j] and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].
* E.g. if triplets[i] = [1, 3, 1] and triplets[j] = [2, 1, 2], triplets[j] will be updated to [max(1, 2), max(3, 1), max(1, 2)] = [2, 3, 2].

Return true if it is possible to obtain target as an element of triplets, or false otherwise.

Example 1:

Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3]

Output: true

Explanation:
Choose the first and second triplets, update the second triplet to be [max(1, 7), max(2, 1), max(3, 1)] = [7, 2, 3].

Example 2:

Input: triplets = [[2,5,6],[1,4,4],[5,7,5]], target = [5,4,6]

Output: false

Constraints:

1 <= triplets.length <= 1000
1 <= ai, bi, ci, x, y, z <= 100

Topics

Array Greedy

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

An important observation is that we can ignore triplets with values greater than the target triplet.

Hint 2

Specifically, if a triplet t has any element greater than the corresponding value in target (i.e., t[0] > target[0], t[1] > target[1], or t[2] > target[2]), we can discard it. This is because using such a triplet in operations would exceed the target values, making it invalid.

Hint 3

Now, from the remaining valid triplets, we only need to check whether the target triplet values exist. Since all values in the valid triplets are less than or equal to the corresponding values in the target triplet, finding the target triplet among them guarantees that we can achieve it.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Iterating through and comparing elements in 2D arrays
Greedy Algorithms - Making locally optimal choices to build a global solution
Sets / Hash Sets - Tracking unique values to verify coverage of required conditions

1. Greedy

Intuition

We are given several triplets and a target triplet.
We can merge triplets by taking the maximum value at each index, and we want to know if it is possible to obtain the target exactly.

A key observation is:

any triplet that has a value greater than the target at any index can never be used, because merging only increases values
so such triplets should be ignored

For the remaining valid triplets:

if a triplet matches the target at a certain index, it can help us reach that target value at that position

If we can find triplets that collectively cover all three indices of the target, then merging them will produce the target.

Algorithm

Initialize an empty set good to track which target indices can be matched.
Iterate through each triplet t:
- If any value in t is greater than the corresponding value in target, skip this triplet
For the remaining triplets:
- Check each index i
- If t[i] == target[i], add index i to the set good
After processing all triplets:
- If all three indices {0, 1, 2} are present in good, return true
- Otherwise, return false

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        good = set()

        for t in triplets:
            if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
                continue
            for i, v in enumerate(t):
                if v == target[i]:
                    good.add(i)
        return len(good) == 3

public 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]) {
                continue;
            }
            for (int i = 0; i < t.length; i++) {
                if (t[i] == target[i]) {
                    good.add(i);
                }
            }
        }
        return good.size() == 3;
    }
}

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        unordered_set<int> good;

        for (const auto& t : triplets) {
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {
                continue;
            }
            for (int i = 0; i < t.size(); i++) {
                if (t[i] == target[i]) {
                    good.insert(i);
                }
            }
        }
        return good.size() == 3;
    }
};

class Solution {
    /**
     * @param {number[][]} triplets
     * @param {number[]} target
     * @return {boolean}
     */
    mergeTriplets(triplets, target) {
        const good = new Set();

        for (const t of triplets) {
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {
                continue;
            }
            for (let i = 0; i < t.length; i++) {
                if (t[i] === target[i]) {
                    good.add(i);
                }
            }
        }
        return good.size === 3;
    }
}

public class Solution {
    public bool MergeTriplets(int[][] triplets, int[] target) {
        HashSet<int> good = new HashSet<int>();

        foreach (var t in triplets) {
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {
                continue;
            }
            for (int i = 0; i < t.Length; i++) {
                if (t[i] == target[i]) {
                    good.Add(i);
                }
            }
        }
        return good.Count == 3;
    }
}

class Solution {
    fun mergeTriplets(triplets: Array<IntArray>, target: IntArray): Boolean {
        val good = HashSet<Int>()

        for (t in triplets) {
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue
            for ((i, v) in t.withIndex()) {
                if (v == target[i]) {
                    good.add(i)
                }
            }
        }
        return good.size == 3
    }
}

class Solution {
    func mergeTriplets(_ triplets: [[Int]], _ target: [Int]) -> Bool {
        var good = Set<Int>()

        for t in triplets {
            if t[0] > target[0] || t[1] > target[1] || t[2] > target[2] {
                continue
            }
            for (i, v) in t.enumerated() {
                if v == target[i] {
                    good.insert(i)
                }
            }
        }

        return good.count == 3
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Greedy (Optimal)

Intuition

We are given several triplets and a target triplet.
When we merge triplets, we take the maximum value at each index, so values can only increase, never decrease.

This leads to an important rule:

Any triplet that has a value greater than the target at any index cannot be used to form the target.

Instead of collecting indices in a set, we can think more directly:

To reach target[0], we need at least one triplet where:
- the first value equals target[0]
- the other two values do not exceed the target
Similarly for target[1] and target[2]

If we can independently satisfy all three positions using valid triplets, then merging those triplets will exactly form the target.

Algorithm

Initialize three boolean flags:
- x → can we match target[0]?
- y → can we match target[1]?
- z → can we match target[2]?
Iterate through each triplet t:
Update the flags:
- Set x = true if:
  - t[0] == target[0]
  - t[1] <= target[1]
  - t[2] <= target[2]
- Set y = true if:
  - t[1] == target[1]
  - t[0] <= target[0]
  - t[2] <= target[2]
- Set z = true if:
  - t[2] == target[2]
  - t[0] <= target[0]
  - t[1] <= target[1]
If at any point all three flags x, y, and z become true:
- return true immediately
If the loop finishes and not all flags are true:
- return false

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        x = y = z = False
        for t in triplets:
            x |= (t[0] == target[0] and t[1] <= target[1] and t[2] <= target[2])
            y |= (t[0] <= target[0] and t[1] == target[1] and t[2] <= target[2])
            z |= (t[0] <= target[0] and t[1] <= target[1] and t[2] == target[2])
            if x and y and z:
                return True
        return False

public class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean x = false, y = false, z = false;
        for (int[] t : triplets) {
            x |= (t[0] == target[0] && t[1] <= target[1] && t[2] <= target[2]);
            y |= (t[0] <= target[0] && t[1] == target[1] && t[2] <= target[2]);
            z |= (t[0] <= target[0] && t[1] <= target[1] && t[2] == target[2]);
            if (x && y && z) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        bool x = false, y = false, z = false;
        for (const auto& t : triplets) {
            x |= (t[0] == target[0] && t[1] <= target[1] && t[2] <= target[2]);
            y |= (t[0] <= target[0] && t[1] == target[1] && t[2] <= target[2]);
            z |= (t[0] <= target[0] && t[1] <= target[1] && t[2] == target[2]);
            if (x && y && z) return true;
        }
        return false;
    }
};

class Solution {
    /**
     * @param {number[][]} triplets
     * @param {number[]} target
     * @return {boolean}
     */
    mergeTriplets(triplets, target) {
        let x = false,
            y = false,
            z = false;
        for (let t of triplets) {
            x |= t[0] === target[0] && t[1] <= target[1] && t[2] <= target[2];
            y |= t[0] <= target[0] && t[1] === target[1] && t[2] <= target[2];
            z |= t[0] <= target[0] && t[1] <= target[1] && t[2] === target[2];
            if (x && y && z) return true;
        }
        return false;
    }
}

public class Solution {
    public bool MergeTriplets(int[][] triplets, int[] target) {
        bool x = false, y = false, z = false;
        foreach (var t in triplets) {
            x |= (t[0] == target[0] && t[1] <= target[1] && t[2] <= target[2]);
            y |= (t[0] <= target[0] && t[1] == target[1] && t[2] <= target[2]);
            z |= (t[0] <= target[0] && t[1] <= target[1] && t[2] == target[2]);
            if (x && y && z) return true;
        }
        return false;
    }
}

class Solution {
    fun mergeTriplets(triplets: Array<IntArray>, target: IntArray): Boolean {
        var x = false
        var y = false
        var z = false

        for (t in triplets) {
            x = x || (t[0] == target[0] && t[1] <= target[1] && t[2] <= target[2])
            y = y || (t[0] <= target[0] && t[1] == target[1] && t[2] <= target[2])
            z = z || (t[0] <= target[0] && t[1] <= target[1] && t[2] == target[2])

            if (x && y && z) return true
        }
        return false
    }
}

class Solution {
    func mergeTriplets(_ triplets: [[Int]], _ target: [Int]) -> Bool {
        var x = false, y = false, z = false

        for t in triplets {
            if t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2] {
                if t[0] == target[0] { x = true }
                if t[1] == target[1] { y = true }
                if t[2] == target[2] { z = true }
            }

            if x && y && z {
                return true
            }
        }

        return false
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Including Triplets With Values Exceeding the Target

A triplet where any element exceeds the corresponding target value can never be used because merging only takes the maximum at each position, so values can only increase. Failing to filter out these invalid triplets leads to incorrect results.

Checking Only for Exact Target Matches Without Filtering

Some solutions check if a triplet matches the target at a position but forget to verify that the other positions do not exceed the target. A triplet like [5, 2, 3] matching target[0] = 5 is useless if target[1] = 1 because the 2 exceeds it.

Thinking You Need to Find a Single Triplet Equaling the Target

The problem allows merging multiple triplets. You do not need one triplet that exactly equals the target. You need to find triplets that collectively can contribute each target value independently while never exceeding any target position.