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
The 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. If all three positions are matched by some triplets, the target can be formed by merging those triplets.
Optimal Approach
Iterate 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. After processing all triplets, check if the set contains all indices {0,1,2}. Return true if yes, false otherwise.
Time
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
| 13 | return len(good) == 3 |
Objective
To determine if all target positions are covered by valid triplets and return the final boolean result.
Key Insight
The merged triplet can only equal the target if every position in the target is matched by at least one triplet that does not exceed the target. Checking that the set contains all three indices confirms this condition. This final check encapsulates the entire problem's correctness in a simple membership test.
Interview Quick-Check
Core Logic
Return true if and only if the set of matched indices contains all three positions, indicating the target can be formed by merging.
State & Boundaries
The length check ensures all positions 0, 1, and 2 are matched; partial coverage is insufficient.
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.
if v == target[i]:Check if the current triplet's value matches the target at this position.
Matching values indicate that this triplet can contribute to forming the target at this position, so the index is recorded.
good.add(i)Add the index of the matching position to the coverage set.
Recording the index in the set tracks which target positions have been matched by valid triplets, enabling a final coverage check.
good = set()Initialize a set to track indices of target positions matched by valid triplets.
This set acts as a coverage tracker, recording which positions in the target triplet have been matched exactly by triplets that do not exceed the target, enabling a constant-space summary of progress.
continueSkip the current triplet if it exceeds the target in any position.
Continuing to the next iteration avoids processing invalid triplets, maintaining correctness and efficiency.
for i, v in enumerate(t):Iterate over each index and value in the current triplet.
Examining each position allows the algorithm to identify which positions match the target exactly, essential for tracking coverage.
for t in triplets:Begin iterating over each triplet in the input list.
Processing each triplet individually allows the algorithm to filter and analyze candidates in a single pass, ensuring linear time complexity.
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?
Because merging takes the maximum at each position, having at least one triplet that matches the target value at each position and does not exceed the target in any position guarantees the merged result can achieve the target exactly.
Related Problems
Greedy 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