Merge Triplets to Form Target
You are given a target triplet and a list of triplets. Each triplet is a list of three integers. You need to determine if it is possible to merge some of the triplets in the list to form the target triplet. A merge is possible if for each corresponding element in the triplets, the maximum of that element in the merged triplets is equal to the corresponding element in the target triplet.
Constraints:
- 1 <= triplets.length <= 100
- triplets[i].length == 3
- 1 <= triplets[i][j] <= 100
- target.length == 3
- 1 <= target[j] <= 100
Examples:
Input: [[2,5,3],[1,8,4],[1,7,5]], [2,7,5]
Output: True
Explanation: We can merge the first and third triplets to get [2,7,5], which is equal to the target triplet.
Input: [[3,4,5],[4,5,6]], [3,4,5]
Output: True
Explanation: We can merge the first triplet to get [3,4,5], which is equal to the target triplet.
Input: [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], [5,5,5]
Output: False
Explanation: It is not possible to merge any of the triplets to get [5,5,5].
Solutions
Greedy
We initialize three variables x, y, z to 0. Then we iterate over each triplet in the list. If the current triplet can be merged (i.e., its elements are less than or equal to the corresponding elements in the target triplet), we update x, y, z to be the maximum of their current values and the corresponding elements in the current triplet. Finally, we return whether x, y, z are equal to the corresponding elements in the target triplet.
bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
int x = 0, y = 0, z = 0;
for (auto& triplet : triplets) {
if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
x = max(x, triplet[0]);
y = max(y, triplet[1]);
z = max(z, triplet[2]);
}
}
return x == target[0] && y == target[1] && z == target[2];
}Follow-up:
What if we can merge the triplets in any order, not just the order they appear in the list?
