Merge Triplets To Form Target Triplet

---

Intuition

• Whenever you have a value in a triplet that is larger than any of the target values, that value cannot be a candidate for selection, since it is impossible to form the target from that point.
• After removal of those triplets, for the remaining triplets, if there exists an element which is equal to the target, then you can always reach that element.
  • This is because you have removed any situation in which this is not the case.

Complexity

Runtime

$O(N)$ since we are looping in range 3 for each of the N triplets.

Space

$O(N)$ to store the candidates

Code

Using Set to Remember Good Candidates

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        good = set()
        for triplet in triplets:
            if any(triplet[i] > target[i] for i in range(3)):
                continue
            for i, v in enumerate(triplet):
                if v == target[i]:
                    good.add(i)
 
        return len(good) == 3

Checking if Remaining Candidates Are Valid

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        candidates = []
        for triplet in triplets:
            if not any(triplet[i] > target[i] for i in range(3)):
                candidates.append(triplet)
        
        is_valid = [False for _ in range(3)]
        for triplet in candidates:
            for i in range(3):
                if triplet[i] == target[i]:
                    is_valid[i] = True
        
        return all(is_valid)

Cards

START Basic Front: Merge Triplets To Form Target Triplet Back: Remove all candidates with any value greater than corresponding target value, then check if target is in the rest. END

---

References

• Merge Triplets To Form Target Triplet