Merge Triplets to Form Target Triplet

The problem

Each item of triplets is a triplet: a list of three positive numbers. target is a triplet too. To merge triplets, take the largest value in each of the three positions, so merging [1, 5, 3] and [4, 2, 3] gives [4, 5, 3]. Return true if you can select one or more of the triplets so that merging them gives exactly target, and false otherwise. A single selected triplet stays as it is.

What to write

function solve(triplets: number[][], target: number[]): boolean

Input
triplets = [[2,5,3],[1,8,4],[1,7,5]]
target = [2,7,5]

Output
true

Input
triplets = [[3,4,5],[4,5,6]]
target = [3,2,5]

Output
false

Constraints

All triples have three positive coordinates.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A triplet has only three positions, so comparing or merging two triplets is a small, fixed amount of work. What grows quickly is the number of selections, because every triplet can be in or out. So look closely at what one merge can and cannot do to a value.

2. Hint 2: Ask a smaller question

   Let target be [2, 7, 5]. Suppose one of the triplets you select is [1, 8, 4]. Whatever else you select, what can you say about the second value of the result? Now suppose you select [1, 7, 5]. Can it ever spoil a result?

3. Hint 3: Name the pattern

   A triplet with a value above target in the same position can never be used, and any other triplet can only help. So nothing has to be weighed up: leave out the first kind and merge all of the second kind. Deciding each item once, by a rule that is always safe, is a greedy choice. Read the lesson on greedy choice.

4. Hint 4: State the invariant

   The merged triplet is never above target in any position. In each position it holds the highest value found so far among the triplets that are not above target anywhere.

5. Hint 5: Sketch the pseudocode

   Start with merged = [0, 0, 0]. For each triplet: if any of its three values is larger than the value of target in the same position, skip it. Otherwise, in each position, keep the larger of the merged value and the value of the triplet. Return true if merged equals target in all three positions.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Discard any triple that exceeds the target in a coordinate. The componentwise maximum of the remaining triples is the best possible result.

The slow way

Try every selection: each triplet is either in it or not. Merge the chosen triplets and compare the result with target. This is correct, but every extra triplet doubles the number of selections. Three triplets have 7 selections that are not empty, and 20 triplets have about a million.

The insight

Merging can raise a value but never lower it. So a triplet with a value above target in the same position is ruled out for good, and every other triplet is harmless: it cannot push the result too high. That leaves nothing to choose: merge all the harmless ones. Deciding each triplet once by a safe rule is a greedy choice.

Step by step

1. Start the merged triplet at zero in every position. Every value in a triplet is positive, so zero is lower than all of them and is replaced by the first triplet merged in. If no triplet is merged, the zeros stay and cannot equal target.
2. Use a triplet only if no value is above target in its position. Merging keeps the larger value, so a value above target would stay in the result whatever else is merged. A triplet with such a value cannot be part of any selection that works.
3. Merge it in: keep the larger value in each position. A triplet that passed the test cannot lift any position above target. Merging it can only bring the result closer, so there is no reason to leave it out.
4. The answer is true only if the merged triplet equals target. The merged triplet holds the highest value each position can reach without going above target. If that equals target, the triplets merged in are a selection that works. If a position is too low, no selection reaches it.

The same numbered steps are the comments in each solution.

function solve(triplets, target) {
  // 1. Start the merged triplet at zero in every position
  const best = [0, 0, 0];
  for (const t of triplets) {
    // 2. Use a triplet only if no value is above target in its position
    if (t.every((n, i) => n <= target[i])) {
      // 3. Merge it in: keep the larger value in each position
      for (let i = 0; i < 3; i++) best[i] = Math.max(best[i], t[i]);
    }
  }
  // 4. The answer is true only if the merged triplet equals target
  return best.every((n, i) => n === target[i]);
}

function solve(triplets: number[][], target: number[]): boolean {
  // 1. Start the merged triplet at zero in every position
  const best = [0, 0, 0];
  for (const t of triplets) {
    // 2. Use a triplet only if no value is above target in its position
    if (t.every((n, i) => n <= target[i])) {
      // 3. Merge it in: keep the larger value in each position
      for (let i = 0; i < 3; i++) best[i] = Math.max(best[i], t[i]);
    }
  }
  // 4. The answer is true only if the merged triplet equals target
  return best.every((n, i) => n === target[i]);
}

def solve(triplets, target):
    # 1. Start the merged triplet at zero in every position
    best = [0, 0, 0]
    for triplet in triplets:
        # 2. Use a triplet only if no value is above target in its position
        if all(part <= goal for part, goal in zip(triplet, target)):
            # 3. Merge it in: keep the larger value in each position
            best = [max(old, part) for old, part in zip(best, triplet)]
    # 4. The answer is true only if the merged triplet equals target
    return best == target

Example 1, traced

Input
triplets = [[2,5,3],[1,8,4],[1,7,5]]
target = [2,7,5]

Output
true

Why it works

A triplet that is left out could not be part of any selection that works. A triplet that is merged can never lift a position above target. So if some selection produces target, adding every other harmless triplet to it changes nothing, and merging all the harmless ones produces target too. That is the one selection the method checks.

Time and space

Time O(n), extra space O(1). One pass reads each of the n triplets once and does a fixed amount of work on its three positions, so the time is O(n). Only the one merged triplet is stored, however many triplets there are: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Test a triplet before you merge it. If every triplet is merged, example 1 gives [2, 8, 5] and the answer false: the 8 from [1, 8, 4] can never be removed again.
• A value equal to the value of target is allowed: it is exactly what you need. If the test asks for smaller values only, example 1 leaves out all three triplets and answers false.
• Finding each value of target somewhere is not enough. With triplets [2, 8, 3] and [1, 7, 5] and target [2, 7, 5], every value is there, but the 2 comes with an 8, so the answer is false.

Pattern

Greedy choice. Builds on Maximum Subarray.

Keep going