Merge Triplets to Form Target
Problem Statement
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]
andtriplets[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
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(1)
space, where n
is the number of triplets.
Hint 1
Consider which triplets could possibly contribute to forming the target. Any triplet with a value greater than the corresponding target value cannot be used.
Hint 2
Iterate through the triplets and check if each value is less than or equal to the corresponding target value. If not, that triplet can’t be used.
Hint 3
Keep track of whether you’ve found a triplet that matches each of the target values in the correct position.
Solution
Greedy
def merge_triplets(triplets: list[list[int]], target: list[int]) -> bool: """ Determines if it's possible to merge triplets to form the target.
Args: triplets: A list of triplets (lists of 3 integers). target: The target triplet (list of 3 integers).
Returns: True if the target can be formed, False otherwise. """ 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
Time complexity: O(n)
Space complexity: O(1)