{x}
blog image

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.

 

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 <= 105
  • triplets[i].length == target.length == 3
  • 1 <= ai, bi, ci, x, y, z <= 1000

Solution Explanation

The problem asks whether it's possible to obtain a target triplet [x, y, z] by applying a specific operation on a list of triplets. The operation involves choosing two triplets and updating one with the element-wise maximum of both. The solution leverages a greedy approach.

Approach:

The core idea is that we only need to consider triplets whose elements are less than or equal to the corresponding elements in the target triplet. This is because taking the maximum will never decrease any element. Therefore, we only need to check if there exist triplets whose elements are less than or equal to the target's respective elements and, through combinations of these, whether we can reach the target.

The algorithm iterates through each triplet. If a triplet's elements are less than or equal to the target's corresponding elements, it updates three variables d, e, and f. d, e, and f track the maximum values encountered for the first, second, and third elements respectively, within the triplets satisfying the condition.

Finally, it checks if d, e, and f are equal to x, y, and z (the target triplet's elements). If they are, it means we can obtain the target triplet by selecting appropriate triplets and performing the operation, returning true. Otherwise, it returns false.

Time Complexity Analysis:

The algorithm iterates through the triplets list once. The max operations within the loop are constant time. Therefore, the overall time complexity is O(n), where n is the number of triplets.

Space Complexity Analysis:

The algorithm uses a constant amount of extra space (d, e, f). Therefore, the space complexity is O(1).

Code Explanation (Python):

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        x, y, z = target # Unpack the target triplet
        d = e = f = 0     # Initialize variables to track maximums
 
        for a, b, c in triplets: #Iterate through each triplet
            if a <= x and b <= y and c <= z: #Check if triplet's elements are <= target's elements
                d = max(d, a)  #Update max values
                e = max(e, b)
                f = max(f, c)
 
        return [d, e, f] == target # Check if we reached the target triplet

The other languages' solutions follow the same logic and have the same time and space complexity. They only differ in syntax.