Medium

Merge Triplets to Form Target Triplet

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 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 (0-indexed) `i` and `j` (`i != j`) and update `triplets[j]` to become `[max(ai, aj), max(bi, bj), max(ci, cj)]`. - For example, if `triplets[i] = [2, 5, 3]` and `triplets[j] = [1, 7, 5]`, `triplets[j]` will be updated to `[max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5]`. Return `true` if it is possible to obtain the `target` triplet `[x, y, z]` as an element of `triplets`, or `false` otherwise.

Examples

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

Output:true

Perform the following operations: - Choose the first and last triplets [2,5,3] and [1,7,5]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]. The target triplet [2,7,5] is now an element of triplets.

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

Output:false

It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.

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

Output:true

Perform the following operations: - Choose the first and third triplets [2,5,3] and [1,2,5]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. - Choose the third and fourth triplets [2,5,5] and [5,2,3]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]]. The target triplet [5,5,5] is now an element of triplets.

Constraints

1 <= triplets.length <= 10^5
triplets[i].length == target.length == 3
1 <= ai, bi, ci, x, y, z <= 1000

Greedy Elimination

Approach

Since the operation always takes the maximum, if a triplet has *any* value strictly greater than the corresponding value in the `target` triplet, it can *never* be used. Using it would permanently ruin our chance of forming the target because the maximum operation only increases values. So, we iterate through all `triplets` and discard any triplet that has `a > target[0]`, `b > target[1]`, or `c > target[2]`. For all the remaining valid triplets, we merge them together by tracking the maximum values we've seen so far for the first, second, and third elements. If our tracked maximums eventually match `target[0]`, `target[1]`, and `target[2]`, we return true.

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Time complexity is O(n) as we only need to iterate through the array of triplets once. Space complexity is O(1) because we only use a few boolean variables or a small set to track progress.

Solution.java

1class Solution {2    public boolean mergeTriplets(int[][] triplets, int[] target) {3        boolean matchFirst = false;4        boolean matchSecond = false;5        boolean matchThird = false;6        7        for (int[] t : triplets) {8            // Discard triplets that have any value greater than the target9            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {10                continue;11            }12            13            // Check if this valid triplet can help us reach the target components14            if (t[0] == target[0]) matchFirst = true;15            if (t[1] == target[1]) matchSecond = true;16            if (t[2] == target[2]) matchThird = true;17            18            // If all three components have been matched at some point, we are good19            if (matchFirst && matchSecond && matchThird) {20                return true;21            }22        }23        24        return false;25    }26}