Merge Triplets to Form Target Triplet

MEDIUM✓ CHIP-TIMEDLC #1899 — FULL STATEMENT ↗

The drill: A pile of coordinate triples can be merged by taking the elementwise max of whichever ones you pick. Decide whether some selection of them merges into an exact target triple.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A collection of coordinate triples arrives alongside one target triple. Any subset of the collection can be merged together by taking, coordinate by coordinate, the maximum value across everything picked.

Merging can only push a coordinate up toward the largest value present among the picks — it never lowers anything. The task is deciding whether some subset of the triples merges into a result matching the target exactly on all three coordinates.

A triplet may be left out of the selection entirely, and the order triples are merged in doesn't affect the outcome — only which ones get included matters.

EX 01

triplets = [[4, 3, 2], [1, 8, 3], [2, 5, 6], [9, 1, 1]] · target = [4, 8, 6]

→ true

THREE CONTRIBUTORS PLUS ONE FILTERED-OUT OVERSHOOT

EX 02

triplets = [[5, 6, 7], [6, 1, 1]] · target = [5, 6, 7]

→ true

ONE EXACT MATCH, ONE INVALID

EX 03

triplets = [[3, 9, 2], [9, 2, 3], [1, 1, 9], [10, 1, 1]] · target = [9, 9, 9]

→ true

EACH COORDINATE MAXED BY A DIFFERENT TRIPLET

each triplet and the target hold exactly three coordinate values
coordinate values are positive integers within a modest range
merging takes the elementwise maximum, which never decreases a coordinate
any subset of the triplets — including skipping some — may be merged

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Merging only ever raises each coordinate toward the maximum of what's picked — it can never lower one. So what disqualifies a triplet from ever being picked?

HINT 2 THE STRUCTURE

Any triplet with a coordinate above the matching target coordinate would push that coordinate past target the moment it's merged in — it's poison, permanently. Only triplets that stay under-or-equal on all three coordinates are usable.

HINT 3 ONE STEP FROM THE ANSWER

Take every usable triplet and fold them together with elementwise max — one linear pass. If the fold lands exactly on target, it's reachable; if any coordinate falls short, no combination fixes it.

COACH'S BOARD — THE PATTERN, STEP BY STEP

FILTER, THEN FOLDPATTERN · GREEDY — ELEMENTWISE MAXtriplets = [[4,3,2],[1,8,3],[2,5,6],[9,1,1]] · target = [4, 8, 6]

4,3,2

1,8,3

2,5,6

9,1,1

BEST SO FAR

best → [0, 0, 0]

STEP 1

Target [4, 8, 6]. Merging only ever raises coordinates — any triplet that overshoots target anywhere is poison and gets skipped.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/merge-triplets-to-form-target-triplet.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        best = [0, 0, 0]
        for t in triplets:
            if t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]:
                best[0] = max(best[0], t[0])
                best[1] = max(best[1], t[1])
                best[2] = max(best[2], t[2])
        return best == target

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 9 LN

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        n = len(triplets)
        for size in range(1, n + 1):
            for combo in itertools.combinations(triplets, size):
                merged = [0, 0, 0]
                for t in combo:
                    for i in range(3):
                        merged[i] = max(merged[i], t[i])
                if merged == target:
                    return True
        return False

TIME O(2^N)SPACE O(N)PYTHON · TRAINING PACE · 12 LN

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        int[] best = new int[3];
        for (int[] t : triplets) {
            if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
                best[0] = Math.max(best[0], t[0]);
                best[1] = Math.max(best[1], t[1]);
                best[2] = Math.max(best[2], t[2]);
            }
        }
        return best[0] == target[0] && best[1] == target[1] && best[2] == target[2];
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 13 LN

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        int n = triplets.length;
        for (int mask = 1; mask < (1 << n); mask++) {
            int[] merged = new int[3];
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    for (int j = 0; j < 3; j++) {
                        merged[j] = Math.max(merged[j], triplets[i][j]);
                    }
                }
            }
            if (merged[0] == target[0] && merged[1] == target[1] && merged[2] == target[2]) {
                return true;
            }
        }
        return false;
    }
}

TIME O(2^N)SPACE O(N)JAVA · TRAINING PACE · 19 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED