The problem
Given triplets [a, b, c] and a target triplet, you may merge two triplets by taking the maximum of each position. Can you end up with exactly the target?
Input: pots (2,5,3) (1,8,4) (1,7,5), target (2,7,5) Output: true
Picture it
Picture paint pots with amounts of red, green and blue. Mixing takes the larger amount of each colour, so it can only ever go up. Any pot with too much of some colour would ruin the mix, so throw it out. From the safe pots, we only need each target amount to appear in some pot.
How to recognise it
- Merging takes the maximum of each position, and the operation can only raise values, never lower them.
- Because a merge can never undo an overshoot, any triplet with a value above the target is poison: using it can never lead to the target.
- Each position is independent: you only need some safe triplet that supplies the exact target value for that position.
- Up to 10^5 triplets, so trying subsets of triplets is impossible; one filtering pass is expected.
Start with brute force
Try every non-empty subset of triplets, merge it with a position-wise maximum, and see whether the result equals the target.
def merge_brute(triplets, target):
n = len(triplets)
for mask in range(1, 1 << n):
cur = [0, 0, 0]
for i in range(n):
if mask >> i & 1:
cur = [max(cur[k], triplets[i][k]) for k in range(3)]
if cur == list(target):
return True
return False
There are 2^n subsets and each merge costs O(n), so time is O(n × 2^n). It is usable for about 20 triplets, and the limit is 10^5. Space is O(1) besides the running triplet.
From brute force to the idea
- A merge only raises values. The result at each position is the largest value among the triplets used. So the final triplet equals the target only if every used triplet is at most the target in all three positions.
- Discard bad triplets. Any triplet with a value above the target at some position can never be used. The code skips it with
continue. - Match positions independently. Among the safe triplets, merging them all gives, at each position, the largest safe value. That equals the target exactly when at least one safe triplet has the target value there.
- Record which positions are covered. For each safe triplet and each position where it equals the target, add the position to a set
got. - Decide. The target can be formed if and only if
gotholds all three positions.
This is the key idea: throw away every triplet that overshoots anywhere, then check that each target position is supplied exactly by some remaining triplet.
The key idea
Ignore triplets exceeding the target anywhere; the rest must cover each target value. O(n).
Python solution
def merge_triplets(triplets, target):
got = set()
for t in triplets:
if any(t[i] > target[i] for i in range(3)):
continue # would overshoot: never use it
for i in range(3):
if t[i] == target[i]:
got.add(i) # this pot supplies slot i exactly
return len(got) == 3In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n × 2^n): every subset is merged | O(1): a running triplet |
| Filter and cover (shown code) | O(n): three comparisons and three equality tests per triplet | O(1): a set of at most three positions |
Edge cases
- No triplets (
[]): returnsFalse, sincegotstays empty. - A triplet equal to the target (
[[1, 1, 1]], target[1, 1, 1]): returnsTrue. - Overshoot is fatal (
[[1, 3, 4], [2, 5, 8]], target[2, 5, 4]): returnsFalse. The second triplet matches two positions but overshoots the third, so it is discarded. - One position never matched (
[[1, 2, 3]], target[1, 2, 4]): returnsFalse. - Matches spread over several triplets (
[[2, 5, 3], [1, 8, 4], [1, 7, 5]], target[2, 7, 5]): returnsTrue;[2, 5, 3]gives position 0,[1, 7, 5]gives positions 1 and 2, and[1, 8, 4]is discarded. - Repeated triplets: harmless; positions are only added to a set.
Common mistakes
- Forgetting to filter, which counts a triplet that overshoots elsewhere (the second example above would return
True). - Requiring one triplet to match all three positions, which rejects valid combinations.
- Comparing with
>=instead of==for coverage, which would accept a safe triplet that is below the target. - Filtering only on positions that already match, instead of all three positions.
Merging now takes the minimum of each position. Can some set of triplets be merged into exactly the target? For [[5, 5, 5], [4, 6, 7]] and target [4, 5, 5] the answer is True (the minimum of the two), and for [[1, 3, 4], [2, 5, 8]] with target [2, 5, 4] it is False. Describe your approach, then write it if you like.
Compare with our answer
Mirror the idea: a merge can only lower values, so any triplet with a value below the target is poison.
def merge_min(triplets, target):
got = set()
for t in triplets:
if any(t[i] < target[i] for i in range(3)):
continue
for i in range(3):
if t[i] == target[i]:
got.add(i)
return len(got) == 3
merge_min([[1, 3, 4], [2, 5, 8]], [2, 5, 4]) is False: the first triplet is below the target in position 0 so it is discarded, and the second matches only positions 0 and 1. merge_min([[5, 5, 5], [4, 6, 7]], [4, 5, 5]) is True. Time O(n), space O(1).
A strong answer mentions: reversing the inequality (discard triplets below the target), the same coverage set, and that the single pass is still O(n).
1. Parts are described by three measurements and merging keeps the per-position maximum. You must decide whether some merge gives exactly a target, with up to 100,000 parts. Which approach fits best?
Merging can only raise values, so any part that overshoots is unusable, and the remaining parts must cover each position exactly. Merging everything includes the bad parts, and subsets are exponential.
2. Why is the shown code O(n) time and O(1) space?
Each triplet costs a constant number of comparisons and got can hold only three entries. It does not sort, tabulate merges, or stop at the first triplet.
3. A learner removes the continue line so that overshooting triplets also count. For which input does the function now return the wrong answer?
Without the filter, [2, 5, 8] is credited with positions 0 and 1 and [1, 3, 4] with position 2, so the code says True; the correct answer is False because [2, 5, 8] overshoots position 2. The other three inputs give the right answer either way.
Score 60% or more and the lesson is marked complete.