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):
i and j (i != j) and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].
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.
Example 1:
Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5] Output: true Explanation: Perform the following operations: - Choose the first and last triplets [[2,5,3],[1,8,4],[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.
Example 2:
Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5] Output: false Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.
Example 3:
Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5] Output: true Explanation: Perform the following operations: - Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. 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,3],[2,3,4],[2,5,5],[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 <= 105triplets[i].length == target.length == 31 <= ai, bi, ci, x, y, z <= 1000We need to check if a valid triplet can be formed using given triplets, by repeatedly performing the merge operation. For a triplet to contribute to the target triplet, each of its values should be less than or equal to the corresponding target value of the target triplet. If a triplet has at least one value that is greater, it cannot contribute to forming the target triplet.
Once a triplet is considered valid, we then track whether each of the three target values can at least be achieved by an individual triplet. If all these conditions are satisfied, the target triplet can be formed.
The function mergeTriplets iterates over each triplet, checking if each element is less than or equal to the corresponding target element. If valid, it updates canAchieve array to true where the triplet matches the target.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the size of the input triplets.
Space Complexity: O(1), as we only use a constant amount of space.
A different approach involves utilizing a set to ensure each element from the target can be built from appropriate triplets. Here, triplets are evaluated, and only those which each value does not exceed target values are considered. We then use sets initialized for each element of the target (x, y, z) to track their achievability.
The combination of these sets at the end deduces whether the target triplet can ultimately be composed through progressive manipulations.
This alternative C solution employs three boolean flags (foundX, foundY, foundZ) to denote if each element of the target can be built from eligible triplets. This aligns with the hash set concept but is adaptive to C's capabilities.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), with n being the count of triplets.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Filter Valid Triplets and Check Feasibility | Time Complexity: O(n), where n is the size of the input triplets. |
| Hash Set Tracking for Each Target Element | Time Complexity: O(n), with n being the count of triplets. |
Merge Triplets to Form Target Triplet - Greedy - Leetcode 1899 - Python • NeetCode • 32,512 views views
Watch 9 more video solutions →Practice Merge Triplets to Form Target Triplet with our built-in code editor and test cases.
Practice on FleetCode