A lot of times with Greedy problems the answer can be very tricky, however with this problem, the answer is pretty intuitive and it’s easy to see that the brute force approach which would potentially be a backtracking approach would be a lot of work, and the time complexity would also be exponential.
Using the greedy method we would simply have to go through each triplet and check if including it in our merge would be beneficial or not. We do this by mapping each index of the triplet to the corresponding index in the target. If they match we can use it, and we would have solved for that index, however, if any index in the triplet is greater than the target we cannot use that triplet, at all. When we get all three indices to match we can return True. For every triplet we keep a set found to keep track of which indices for that triplet match the target, if we don’t find an index that doesn’t work, we can union found with another set totalFound which keeps track of indices that have been found so far, if the length of this index becomes 3, we return True. We need two sets because there is a chance, that some index that matches a particular triplet cannot be used because another index is greater than the target. Finally, we return False if we can never get the length of totalFound to be 3.
class Solution: def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool: # T: O(n) S: O(1) totalFound = set() for triplet in triplets: found = set() for i in range(3): if triplet[i] == target[i]: found.add(i) elif triplet[i] > target[i]: break else: totalFound = totalFound.union(found) if len(totalFound) == 3: return True return False
The time complexity of this approach is O(3n) which simplifies to O(n) and the space complexity is O(3) which simplifies to O(1).