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
01
- Input
triplets = [[2, 5, 3], [1, 8, 4], [1, 7, 5]], target = [2, 7, 5]
- Output
true
02
- Input
triplets = [[3, 4, 5], [4, 5, 6]], target = [3, 2, 5]
- Output
false
03
- 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
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)