Merge Triplets to Form Target Triplet

Merge Triplets to Form Target sounds scary at first. The word merge makes people think they must try every combination. But the real test is simpler. Can you throw away the triplets that would ruin your answer? Once you see which ones are safe to keep, the problem almost solves itself.

🎯 The Problem

You get a list of triplets and one target. You want to build a triplet that exactly equals the target.

• A triplet is three numbers, like [2, 5, 3].
• One move: pick any two triplets and merge them.
• Merge takes the larger value in each of the three slots.
• So merging [2, 5, 3] and [1, 8, 4] gives [2, 8, 4].
• You return true if you can build the target, else false.

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

Explanation: merge [1,7,5] and [2,5,3] to get [2,7,5]

Notice one thing about merging. The numbers can only go up or stay the same. The merge takes the larger value. So a value can never shrink. That single fact decides everything.

Here is the shape of the problem. We merge by taking the max in each slot.

🐢 Approach 1: Try Every Merge Order (Brute Force)

The idea in one line: merge triplets in every possible order and check if any result equals the target.

The idea:

• Merge every pair, then every triple, then more.
• After each merge, compare the result to the target.
• Return true the moment one matches.

Why it is weak:

• The count of merge orders grows fast with the list.
• You repeat the same merges again and again.
• The time becomes unusable on a big list.
• It also hides the simple rule the problem really has.

Here is the subset-style brute-force code:

def merge_triplets(triplets, target):
    n = len(triplets)
    for mask in range(1, 1 << n):
        merged = [0, 0, 0]
        for i in range(n):
            if mask & (1 << i):
                for j in range(3):
                    merged[j] = max(merged[j], triplets[i][j])
        if merged == target:
            return True
    return False

⚡ Approach 2: Greedy Filter (Best)

The idea in one line: throw away the triplets that would overshoot the target, then check if the rest can cover every slot.

The idea:

• Merge only ever takes the larger value per slot.
• So a value above the target can never come back down.
• A triplet with any value above the target is poison.
• A valid triplet is one where no value beats the target.

How it works:

• Keep one flag per slot, all starting as not reached.
• Walk each triplet. Skip it if any value beats the target.
• For a valid triplet, check each slot.
• If its value equals the target there, mark that slot reached.
• At the end, return true only if all three slots were reached.

Why it works:

• Different valid triplets can fill different slots.
• Merging all valid ones never pushes a slot past the target.
• So if each slot value appears once, the merge lands exactly on target.

Why it is fast:

• One pass over the triplets.
• Fixed work per triplet. So the time is O(n).

Here is a dry run of the greedy filter on our example.

Steps to Solve

1. Track three flags, one per slot, all starting as not reached.
2. Walk through each triplet in the list.
3. Skip the triplet if any of its three values is larger than the target value in that slot.
4. For each kept triplet, check each slot. If its value equals the target value there, mark that slot as reached.
5. After all triplets, return true if all three slots were reached, otherwise false.

#include <stdio.h>

int mergeTriplets(int triplets[][3], int n, int target[3]) {
    int hit0 = 0, hit1 = 0, hit2 = 0;   // one flag per slot

    for (int i = 0; i < n; i++) {
        // skip a triplet that exceeds the target in any slot
        if (triplets[i][0] > target[0]) continue;
        if (triplets[i][1] > target[1]) continue;
        if (triplets[i][2] > target[2]) continue;

        if (triplets[i][0] == target[0]) hit0 = 1;  // slot 0 reached
        if (triplets[i][1] == target[1]) hit1 = 1;  // slot 1 reached
        if (triplets[i][2] == target[2]) hit2 = 1;  // slot 2 reached
    }

    return hit0 && hit1 && hit2;        // all three slots reached?
}

int main(void) {
    int triplets[3][3] = {{2, 5, 3}, {1, 8, 4}, {1, 7, 5}};
    int target[3] = {2, 7, 5};
    printf("%s\n", mergeTriplets(triplets, 3, target) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
using namespace std;

bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
    bool hit0 = false, hit1 = false, hit2 = false;  // one flag per slot

    for (auto& t : triplets) {
        // skip a triplet that exceeds the target in any slot
        if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;

        if (t[0] == target[0]) hit0 = true;  // slot 0 reached
        if (t[1] == target[1]) hit1 = true;  // slot 1 reached
        if (t[2] == target[2]) hit2 = true;  // slot 2 reached
    }

    return hit0 && hit1 && hit2;             // all three slots reached?
}

int main() {
    vector<vector<int>> triplets = {{2, 5, 3}, {1, 8, 4}, {1, 7, 5}};
    vector<int> target = {2, 7, 5};
    cout << (mergeTriplets(triplets, target) ? "true" : "false") << endl;
    return 0;
}

true

public class MergeTriplets {
    public static boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean hit0 = false, hit1 = false, hit2 = false;  // one flag per slot

        for (int[] t : triplets) {
            // skip a triplet that exceeds the target in any slot
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;

            if (t[0] == target[0]) hit0 = true;  // slot 0 reached
            if (t[1] == target[1]) hit1 = true;  // slot 1 reached
            if (t[2] == target[2]) hit2 = true;  // slot 2 reached
        }

        return hit0 && hit1 && hit2;             // all three slots reached?
    }

    public static void main(String[] args) {
        int[][] triplets = {{2, 5, 3}, {1, 8, 4}, {1, 7, 5}};
        int[] target = {2, 7, 5};
        System.out.println(mergeTriplets(triplets, target) ? "true" : "false");
    }
}

true

def merge_triplets(triplets, target):
    reached = set()                      # which slots we have matched

    for t in triplets:
        # skip a triplet that exceeds the target in any slot
        if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
            continue
        for i in range(3):               # check all three slots
            if t[i] == target[i]:        # this slot hits the target value
                reached.add(i)

    return len(reached) == 3             # all three slots reached?


triplets = [[2, 5, 3], [1, 8, 4], [1, 7, 5]]
target = [2, 7, 5]
print(merge_triplets(triplets, target))

True

function mergeTriplets(triplets, target) {
  const reached = new Set(); // which slots we have matched

  for (const t of triplets) {
    // skip a triplet that exceeds the target in any slot
    if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) continue;
    for (let i = 0; i < 3; i++) {
      if (t[i] === target[i]) reached.add(i); // this slot hits the target
    }
  }

  return reached.size === 3; // all three slots reached?
}

const triplets = [
  [2, 5, 3],
  [1, 8, 4],
  [1, 7, 5],
];
const target = [2, 7, 5];
console.log(mergeTriplets(triplets, target));

true

Let us read the Python version line by line, because the logic is short but the why matters.

We start with reached = set(). This set holds the slot positions we have already matched. We need slots 0, 1, and 2 to all show up by the end.

Then we loop over each triplet t. The first check is the filter. if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]. If any value is larger than the target in that slot, this triplet is poison. Merging it in would push a slot above the target and we could never fix it. So we continue and skip it.

If the triplet survives the filter, it is a valid triplet. Then the inner loop for i in range(3) checks each slot. If t[i] == target[i], that slot can be filled to exactly the target value by this triplet. So we reached.add(i).

At the end return len(reached) == 3. If all three slots were reached by some valid triplet, merging all the valid ones lifts each slot to exactly the target. So the answer is True. If even one slot is missing, no merge can ever fill it, so the answer is False.

⏱️ Time and Space Complexity

The brute force tries many merge orders, so its time becomes unusable fast. The greedy version looks at each triplet once and does a fixed amount of work per triplet. So it runs in O(n) time. The only extra space is the small set of reached slots, which never holds more than three items.

🧩 Key Takeaways

• ✅ Merging takes the larger value per slot, so a value can never shrink.
• ✅ Any triplet bigger than the target in any slot is poison, so throw it away.
• ✅ A valid triplet is one where every value is at most the target value.
• ✅ Each target slot value must appear in some valid triplet for the answer to be true.
• ✅ One pass over the triplets gives the answer in O(n) time.

🚀 What’s Next?

• Hand of Straights
• Valid Parenthesis String