Merge Triplets to Form Target
Problem
Given a list of triplets and a target triplet, return true if it is possible to select some triplets and merge them to form the target triplet, where merging means taking the maximum value for each position among the selected triplets.
- 1 ≤ triplets.length ≤ 10⁵
- triplets[i].length == 3
- 1 ≤ triplets[i][j], target[j] ≤ 1000
Example
triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]trueThe algorithm iterates through each triplet and filters out those that exceed the target in any position, as they cannot contribute to forming the target. For example, [1,8,4] is discarded because 8 > 7 at index 1. The remaining triplets are checked for positions where their value matches the target exactly. The indices of these matches are collected in a set. After processing all triplets, if the set contains all three indices (0, 1, and 2), it means the target can be formed by merging these triplets, so the function returns true.
Approach
Straightforward Solution
A brute-force approach might try all subsets of triplets and merge them to check if the target can be formed, which is exponential and infeasible for large inputs.
Core Observation
To form the target triplet by merging, each position in the target must be matched by at least one triplet that does not exceed the target in any position and has the exact target value at that position.
Path to Optimal
PreviewThe key insight is to discard any triplet that exceeds the target in any position, as it can never contribute to forming the target. Then, track which positions in the target are matched exactly by the remaining triplets…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate through each triplet, skip those that exceed the target in any position. For the valid triplets, add the indices of positions where the triplet matches the target value to a set…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm iterates through all triplets once, performing constant-time checks and set insertions per triplet, resulting in linear time complexity relative to the number of triplets.
Space
O(1)
The auxiliary space is constant because the set stores at most three indices corresponding to the triplet positions, independent of input size.
Pattern Spotlight
Greedy Algorithms (Selective Filtering and Coverage)
When merging elements to form a target under constraints, greedily discard invalid candidates early and track coverage of required target positions to confirm feasibility without exhaustive search.
Solution
| 1 | class Solution:
|
| 2 | def mergeTriplets(self, triplets: list[list[int]], target: list[int]) -> bool:
|
| 3 | good = set()
|
| 4 |
|
| 5 | for t in triplets:
|
| 6 | if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
|
| 7 | continue
|
| 8 |
|
| 9 | for i, v in enumerate(t):
|
| 10 | if v == target[i]:
|
| 11 | good.add(i)
|
| 12 |
|
| 13 | return len(good) == 3 |
Step-by-Step Solution
Filter Triplets and Track Target Position Matches
| 3 | good = set()
|
| 5 | for t in triplets:
|
| 6 | if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
|
| 7 | continue
|
| 9 | for i, v in enumerate(t):
|
| 10 | if v == target[i]:
|
| 11 | good.add(i)
|
Objective
To iterate through triplets, discard those exceeding the target, and record which target positions are matched exactly by valid triplets.
Key Insight
Discarding triplets that exceed the target in any position ensures only candidates that can contribute to forming the target remain. Tracking exact matches per position allows the algorithm to confirm coverage of all target positions without merging explicitly. This selective filtering and coverage tracking reduces the problem from exponential subset checking to a simple linear scan with set membership.
Interview Quick-Check
Core Logic
Skip triplets that exceed the target in any position to ensure only valid contributors are considered, then add indices of positions where triplet values equal the target to a set to track coverage.
State & Boundaries
The set stores indices 0, 1, and 2 corresponding to triplet positions; the algorithm returns true only if all three are present.
Common Pitfalls & Bugs
Failing to skip triplets that exceed the target can lead to incorrect results, as such triplets cannot be part of a valid merge.
Complexity
This approach runs in O(n) time and O(1) space, suitable for large input sizes.
Return Result Based on Complete Coverage of Target Positions
To determine if all target positions are covered by valid triplets and return the final boolean result.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
return len(good) == 3Return true if all three target positions are matched by valid triplets, false otherwise.
This line encapsulates the entire problem's correctness: only if all positions are matched can the merged triplet equal the target, making this the decisive condition.
if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:Check if the current triplet exceeds the target in any position.
This conditional is critical because it enforces the problem's constraint that merged values cannot exceed the target; skipping invalid triplets prevents false positives.
Full line-by-line criticality + rationale for all 8 lines available on Pro.
Test Your Understanding
Why is it sufficient to check that each position in the target is matched by at least one valid triplet rather than merging all triplets explicitly?
See the answer with Pro.
Related Problems
Greedy Algorithms pattern
Don't just read it. Drill it.
Reconstruct Merge Triplets to Form Target from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Merge Triplets to Form Target drill