Merge Triplets to Form Target Triplet
MediumGreedy
You are given a list triplets, where each triplets[i] = [a_i, b_i, c_i] is a list of three integers, and a target = [x, y, z].
You may apply the following operation any number of times (including zero): pick two different indices i and j, and replace triplets[j] with the position-wise maximum of the two, [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)]. triplets[i] is left unchanged.
Return True if, after some sequence of operations, target appears as one of the triplets in the list. Otherwise return False.
Example 1
- Input:
- triplets = [[5, 1, 1], [2, 3, 1], [2, 1, 4]], target = [2, 3, 4]
- Output:
- True
- Explanation
[5, 1, 1]has a 5 where the target needs 2, and merging can never lower a value, so it is useless. Merging[2, 3, 1]into[2, 1, 4]gives[2, 3, 4], the target.
Example 2
- Input:
- triplets = [[1, 2, 3], [1, 2, 4]], target = [1, 3, 4]
- Output:
- False
- Explanation
- Both triplets are safe to use, but neither has a 3 in the middle position. A merge only ever picks values that are already there, so the middle can never become 3.
Example 3
- Input:
- triplets = [[4, 4, 4]], target = [3, 3, 3]
- Output:
- False
- Explanation
- The only triplet already exceeds the target in every position, and with a single triplet no merge is even possible.
Constraints
- 1 ≤
triplets.length≤ 105 triplets[i].length == target.length == 3- 1 ≤
a_i,b_i,c_i,x,y,z≤ 1000