The problem
Merging two triplets [a, b, c] replaces one of them with [max(a₁, a₂), max(b₁, b₂), max(c₁, c₂)] — the larger value in each position.
Given a list of triplets and a target, return true if some merges can make one triplet equal to target.
Examples
- Input
triplets = [[2, 5, 3], [1, 8, 4], [1, 7, 5]], target = [2, 7, 5]
- Output
true
- Input
triplets = [[3, 4, 5], [4, 5, 6]], target = [3, 2, 5]
- Output
false
- Input
triplets = [[2, 5, 3], [2, 3, 4], [1, 2, 5], [5, 2, 3]], target = [5, 5, 5]
- Output
true
Constraints
- 1 ≤ triplets.length ≤ 10⁵
- 1 ≤ every value ≤ 1000
The idea
Merging can only raise values. So a triplet with any value above the target’s in that position can never be part of the answer — it would push that position too high for good. Ignore it.
Every other triplet is safe: merging it in never overshoots. Merge them all (just track, for each of the three positions, whether some safe triplet matches the target there). The target is reachable exactly when all three positions are matched.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool: # A triplet with any value above the target's can never be used: merging only raises. # Merge every other one; the target is reachable exactly when each position is hit. got = [False, False, False] for t in triplets: if all(t[i] <= target[i] for i in range(3)): for i in range(3): if t[i] == target[i]: got[i] = True return all(got)