127.Merge Triplets to Form Target Triplet

MediumGreedy · 6/8

Problem

You are given a 2D array triplets where triplets[i] = [ai, bi, ci], and a target = [x, y, z].

You may repeatedly pick two indices i and j and replace triplets[j] with [max(ai, aj), max(bi, bj), max(ci, cj)]. Return true if it is possible to make target appear as an element of triplets, otherwise false.

Examples

Input:  triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Merge [2,5,3] and [1,7,5] -> [2,7,5].

Input:  triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: Every triplet has a second value > 2, so any merge has b > 2.

Input:  triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Merge [2,5,3], [1,2,5] and [5,2,3] -> [5,5,5].

Constraints

1 <= triplets.length <= 10^5
triplets[i].length == target.length == 3
1 <= ai, bi, ci, x, y, z <= 1000

💡 Key Insight

A merge takes element-wise maxima, so values can only go up. Any triplet with some value greater than the target in the same position is poison — using it would overshoot forever, so ignore it. Every remaining ("safe") triplet can be merged freely without harm. The answer is true exactly when the safe triplets, taken together, hit x, y and z in their respective positions.

Brute Force over Subsets

TimeO(2^n · n)SpaceO(1).

Intuition

The result of merging a set of triplets is just the element-wise max of the set, regardless of order. So try every non-empty subset, compute its element-wise max, and check whether it equals target. This is only feasible for tiny inputs, but it makes the structure of the problem clear.

Algorithm

For each bitmask mask from 1 to 2^n - 1:
Compute [maxA, maxB, maxC] over triplets whose bit is set.
If it equals target, return true.
Return false.

Visualization

triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
mask 001 -> [2,5,3]        no
mask 010 -> [1,8,4]        no
mask 101 -> [2,7,5]        yes -> true

Code

java

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        int n = triplets.length;
        if (n > 20) {
            return greedy(triplets, target); // subsets are infeasible beyond this size
        }
        for (int mask = 1; mask < (1 << n); mask++) {
            int a = 0, b = 0, c = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    a = Math.max(a, triplets[i][0]);
                    b = Math.max(b, triplets[i][1]);
                    c = Math.max(c, triplets[i][2]);
                }
            }
            if (a == target[0] && b == target[1] && c == target[2]) {
                return true;
            }
        }
        return false;
    }

    // fallback so the method stays correct on large inputs
    private boolean greedy(int[][] triplets, int[] target) {
        int a = 0, b = 0, c = 0;
        for (int[] t : triplets) {
            if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
                a = Math.max(a, t[0]);
                b = Math.max(b, t[1]);
                c = Math.max(c, t[2]);
            }
        }
        return a == target[0] && b == target[1] && c == target[2];
    }
}

Complexity

Time: O(2^n · n) — every subset, each scanned in O(n).
Space: O(1).

Filter, Then Check Each PositionOptimal

TimeO(n)SpaceO(1).

Intuition

Discard every triplet with any value larger than the target at the same position. For the remaining safe triplets, we only need to know whether some safe triplet has a == x, some has b == y, and some has c == z — they can be different triplets, because merging all of them together keeps every value <= target while reaching each target value. Three booleans suffice.

Algorithm

foundX = foundY = foundZ = false.
For each triplet t: skip it if t[0] > x or t[1] > y or t[2] > z.
Otherwise set foundX |= t[0] == x, foundY |= t[1] == y, foundZ |= t[2] == z.
Return foundX && foundY && foundZ.

Dry Run

flowchart TD
    T["target = [5,5,5]"] --> A["[2,5,3]: safe<br/>matches y"]
    T --> B["[2,3,4]: safe<br/>matches nothing"]
    T --> C["[1,2,5]: safe<br/>matches z"]
    T --> D["[5,2,3]: safe<br/>matches x"]
    A --> R["foundX, foundY, foundZ all true<br/>return true"]
    C --> R
    D --> R

target = [3,2,5], triplets = [[3,4,5],[4,5,6]]
[3,4,5]: 4 > 2 -> skip
[4,5,6]: 4 > 3 -> skip
no safe triplets -> false

Code

java

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean foundX = false, foundY = false, foundZ = false;
        for (int[] t : triplets) {
            // any value above the target would overshoot permanently
            if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) {
                continue;
            }
            foundX |= t[0] == target[0];
            foundY |= t[1] == target[1];
            foundZ |= t[2] == target[2];
            if (foundX && foundY && foundZ) {
                return true; // early exit
            }
        }
        return false;
    }
}

Complexity

Time: O(n) — one pass.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Brute Force over Subsets	O(2^n · n)	O(1)
Filter, Then Check Each Position	O(n)	O(1)

Common Pitfalls

Requiring a single triplet to match all three positions — different safe triplets may supply x, y and z.
Counting a match from a triplet that has another value above the target (e.g. [2,8,5] cannot supply x = 2 for target [2,7,5]).
Thinking merge order matters — element-wise max is associative and commutative.
Forgetting that a triplet equal to target on its own is already a valid answer (it is handled naturally).