Merge Triplets to Form Target Triplet
Merging Triplets to Form a Target Triplet
The Merge Triplets to Form Target problem involves determining whether you can construct a specific triplet using a series of merging operations on given triplets.
This article will guide you through understanding the problem, breaking it down, and implementing an efficient solution.
Problem Description
Input
- triplets: A 2D list where each triplet is of the form [a, b, c].
- target: A triplet [x, y, z] that we aim to construct.
Operation
For two triplets triplets[i] = [ai, bi, ci] and triplets[j] = [aj, bj, cj], you can update triplets[j] as follows:
triplets[j]=[max(ai,aj),max(bi,bj),max(ci,cj)]
Goal
Determine whether it is possible to make target an element of triplets after performing the allowed operations.
Example 1
Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3]
Output: true
Explanation:
The cards can be rearranged as [1,2,3,4] and [2,3,4,5].
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
There are mainly two approach to solve this problem –
- Greedy
- Greedy (Optimal)
1. Greedy
- Time complexity: O(n)
- Space complexity: O(1)
Python
C++
Java
JavaScript
Python
class Solution:
def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
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) == 3C++
class Solution {
public:
bool isNStraightHand(vector& hand, int groupSize) {
if (hand.size() % groupSize != 0) return false;
unordered_map count;
for (int num : hand) count[num]++;
sort(hand.begin(), hand.end());
for (int num : hand) {
if (count[num] > 0) {
for (int i = num; i < num + groupSize; i++) {
if (count[i] == 0) return false;
count[i]--;
}
}
}
return true;
}
}; Java
public class Solution {
public boolean mergeTriplets(int[][] triplets, int[] target) {
Set good = new HashSet<>();
for (int[] t : triplets) {
if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {
continue;
}
for (int i = 0; i < t.length; i++) {
if (t[i] == target[i]) {
good.add(i);
}
}
}
return good.size() == 3;
}
} JavaScript
class Solution {
/**
* @param {number[][]} triplets
* @param {number[]} target
* @return {boolean}
*/
mergeTriplets(triplets, target) {
const good = new Set();
for (const t of triplets) {
if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {
continue;
}
for (let i = 0; i < t.length; i++) {
if (t[i] === target[i]) {
good.add(i);
}
}
}
return good.size === 3;
}
}2. Greedy (Optimal)
Time & Space Complexity
- Time complexity: O(
- Space complexity: O(1)
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool mergeTriplets(vector>& triplets, vector& target) {
bool x = false, y = false, z = false;
for (const auto& t : triplets) {
x |= (t[0] == target[0] && t[1] <= target[1] && t[2] <= target[2]);
y |= (t[0] <= target[0] && t[1] == target[1] && t[2] <= target[2]);
z |= (t[0] <= target[0] && t[1] <= target[1] && t[2] == target[2]);
if (x && y && z) return true;
}
return false;
}
}; Java
public class Solution {
public boolean mergeTriplets(int[][] triplets, int[] target) {
boolean x = false, y = false, z = false;
for (int[] t : triplets) {
x |= (t[0] == target[0] && t[1] <= target[1] && t[2] <= target[2]);
y |= (t[0] <= target[0] && t[1] == target[1] && t[2] <= target[2]);
z |= (t[0] <= target[0] && t[1] <= target[1] && t[2] == target[2]);
if (x && y && z) {
return true;
}
}
return false;
}
}
Python
class Solution:
def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
x = y = z = False
for t in triplets:
x |= (t[0] == target[0] and t[1] <= target[1] and t[2] <= target[2])
y |= (t[0] <= target[0] and t[1] == target[1] and t[2] <= target[2])
z |= (t[0] <= target[0] and t[1] <= target[1] and t[2] == target[2])
if x and y and z:
return True
return FalseJavaScript
class Solution {
/**
* @param {number[][]} triplets
* @param {number[]} target
* @return {boolean}
*/
mergeTriplets(triplets, target) {
let x = false, y = false, z = false;
for (let t of triplets) {
x |= (t[0] === target[0] && t[1] <= target[1] && t[2] <= target[2]);
y |= (t[0] <= target[0] && t[1] === target[1] && t[2] <= target[2]);
z |= (t[0] <= target[0] && t[1] <= target[1] && t[2] === target[2]);
if (x && y && z) return true;
}
return false;
}
}
