LeetCode 1899 · Greedy

Merge Triplets to Form Target Triplet, explained with a picture

Mixing paint pots without overshooting a colour.

MediumGreedy
▶ Watch it step by step

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

  1. 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.
  2. Discard bad triplets. Any triplet with a value above the target at some position can never be used. The code skips it with continue.
  3. 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.
  4. Record which positions are covered. For each safe triplet and each position where it equals the target, add the position to a set got.
  5. Decide. The target can be formed if and only if got holds 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) == 3

In 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

ApproachTimeSpace
Brute forceO(n × 2^n): every subset is mergedO(1): a running triplet
Filter and cover (shown code)O(n): three comparisons and three equality tests per tripletO(1): a set of at most three positions

Edge cases

  • No triplets ([]): returns False, since got stays empty.
  • A triplet equal to the target ([[1, 1, 1]], target [1, 1, 1]): returns True.
  • Overshoot is fatal ([[1, 3, 4], [2, 5, 8]], target [2, 5, 4]): returns False. 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]): returns False.
  • Matches spread over several triplets ([[2, 5, 3], [1, 8, 4], [1, 7, 5]], target [2, 7, 5]): returns True; [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.
Your turn: merge with the minimum

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).

Check what stuck

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?

2. Why is the shown code O(n) time and O(1) space?

3. A learner removes the continue line so that overshooting triplets also count. For which input does the function now return the wrong answer?

Score 60% or more and the lesson is marked complete.