1899. Merge Triplets to Form Target Triplet - Solution

The problem

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [a_i, b_i, c_i] describes the i^th triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.

To obtain target, you may apply the following operation on triplets any number of times (possibly zero):

Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)].
- For example, if triplets[i] = [2, 5, 3] and triplets[j] = [1, 7, 5], triplets[j] will be updated to [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5].

Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

Example 1:

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.

Example 2:

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.

Example 3:

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]].
- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]].
The target triplet [5,5,5] is now an element of triplets.

Constraints:

1 <= triplets.length <= 10⁵
triplets[i].length == target.length == 3
1 <= a_i, b_i, c_i, x, y, z <= 1000

Approach overview

Problem Overview: You are given multiple triplets and a target triplet. You can merge any number of triplets by taking the maximum value at each index. The task is to determine whether some sequence of merges can produce the exact target triplet.

The merge operation effectively behaves like a coordinate-wise max. If you merge two triplets [a,b,c] and [x,y,z], the result becomes [max(a,x), max(b,y), max(c,z)]. The challenge is deciding whether some subset of the given triplets can combine to reach the target without exceeding any component.

Approach 1: Filter Valid Triplets and Check Feasibility (Greedy) (Time: O(n), Space: O(1))

This approach relies on a simple greedy observation: any triplet containing a value larger than the corresponding value in the target can never be part of a valid merge. Merging it would permanently push that coordinate beyond the target. Start by iterating through the list and ignore any triplet where triplet[i] > target[i] for any index.

For every remaining valid triplet, track whether it helps achieve one of the three target coordinates. If a triplet matches the target value at index 0, 1, or 2, mark that coordinate as achievable. Because merging uses the maximum operation, as long as each coordinate of the target appears in some valid triplet, combining them will eventually produce the exact target.

This method performs a single pass through the input array, using constant extra variables to track progress. The greedy filter ensures that every considered triplet keeps the merge result within the target bounds. This pattern appears frequently in greedy problems where invalid candidates must be discarded early.

Approach 2: Hash Set Tracking for Each Target Element (Time: O(n), Space: O(1))

This variation tracks which indices of the target have already been satisfied using a small hash set. Iterate through the triplets and discard any triplet that exceeds the target in any coordinate. For valid triplets, check each index and insert the index into the set if the value equals the target's value at that position.

The key idea is that you only need one contributing triplet per coordinate. Once indices 0, 1, and 2 appear in the set, the target triplet can be constructed through merges. Hash lookups keep the check constant time while making the logic explicit and easy to reason about.

This approach still runs in linear time because each triplet is processed once. The extra structure is tiny (at most three entries), so space complexity remains constant. It is a clean implementation choice when solving problems involving arrays combined with lightweight hash table tracking.

Recommended for interviews: The greedy filtering approach is typically what interviewers expect. It shows you recognized the key invariant: no triplet may exceed the target. Explaining that observation clearly demonstrates strong problem decomposition. The hash set variation is equally optimal but mostly improves code clarity rather than algorithmic performance.

Approach 1: Filter Valid Triplets and Check Feasibility

We need to check if a valid triplet can be formed using given triplets, by repeatedly performing the merge operation. For a triplet to contribute to the target triplet, each of its values should be less than or equal to the corresponding target value of the target triplet. If a triplet has at least one value that is greater, it cannot contribute to forming the target triplet.

Once a triplet is considered valid, we then track whether each of the three target values can at least be achieved by an individual triplet. If all these conditions are satisfied, the target triplet can be formed.

Python

def mergeTriplets(triplets, target):
    canAchieve = [False, False, False]
    for triplet in triplets:
        if triplet[0] <= target[0] and triplet[1] <= target[1] and triplet[2] <= target[2]:
            if triplet[0] == target[0]:
                canAchieve[0] = True
            if triplet[1] == target[1]:
                canAchieve[1] = True
            if triplet[2] == target[2]:
                canAchieve[2] = True
    return all(canAchieve)

Java

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean[] canAchieve = new boolean[3];
        for (int[] triplet : triplets) {
            if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
                if (triplet[0] == target[0]) canAchieve[0] = true;
                if (triplet[1] == target[1]) canAchieve[1] = true;
                if (triplet[2] == target[2]) canAchieve[2] = true;
            }
        }
        return canAchieve[0] && canAchieve[1] && canAchieve[2];
    }
}

C++

#include <vector>
using namespace std;

bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
    vector<bool> canAchieve(3, false);
    for (auto& triplet : triplets) {
        if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
            if (triplet[0] == target[0]) canAchieve[0] = true;
            if (triplet[1] == target[1]) canAchieve[1] = true;
            if (triplet[2] == target[2]) canAchieve[2] = true;
        }
    }
    return canAchieve[0] && canAchieve[1] && canAchieve[2];
}

JavaScript

function mergeTriplets(triplets, target) {
    let canAchieve = [false, false, false];
    for (let triplet of triplets) {
        if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
            if (triplet[0] == target[0]) canAchieve[0] = true;
            if (triplet[1] == target[1]) canAchieve[1] = true;
            if (triplet[2] == target[2]) canAchieve[2] = true;
        }
    }
    return canAchieve.every(flag => flag);
}

#include <stdbool.h>

bool mergeTriplets(int** triplets, int tripletsSize, int* tripletsColSize, int* target, int targetSize) {
    bool canAchieve[3] = {false, false, false};
    
    for (int i = 0; i < tripletsSize; ++i) {
        int *triplet = triplets[i];
        if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
            if (triplet[0] == target[0]) canAchieve[0] = true;
            if (triplet[1] == target[1]) canAchieve[1] = true;
            if (triplet[2] == target[2]) canAchieve[2] = true;
        }
    }

    return canAchieve[0] && canAchieve[1] && canAchieve[2];
}

public class Solution {
    public bool MergeTriplets(int[][] triplets, int[] target) {
        bool[] canAchieve = new bool[3];
        foreach(var triplet in triplets) {
            if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
                if (triplet[0] == target[0]) canAchieve[0] = true;
                if (triplet[1] == target[1]) canAchieve[1] = true;
                if (triplet[2] == target[2]) canAchieve[2] = true;
            }
        }
        return canAchieve[0] && canAchieve[1] && canAchieve[2];
    }
}

The Python solution iterates over the triplets filtering those valid under max condition and marks if each corresponding element equals that of the target.

Complexity

Time Complexity: O(n), n being the number of triplets.
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Hash Set Tracking for Each Target Element

A different approach involves utilizing a set to ensure each element from the target can be built from appropriate triplets. Here, triplets are evaluated, and only those which each value does not exceed target values are considered. We then use sets initialized for each element of the target (x, y, z) to track their achievability.

The combination of these sets at the end deduces whether the target triplet can ultimately be composed through progressive manipulations.

Python

def mergeTriplets(triplets, target):
    foundX, foundY, foundZ = False, False, False
    for triplet in triplets:
        if triplet[0] <= target[0] and triplet[1] <= target[1] and triplet[2] <= target[2]:
            if triplet[0] == target[0]:
                foundX = True
            if triplet[1] == target[1]:
                foundY = True
            if triplet[2] == target[2]:
                foundZ = True
    return foundX and foundY and foundZ

Java

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean foundX = false, foundY = false, foundZ = false;
        for (int[] triplet : triplets) {
            if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
                if (triplet[0] == target[0]) foundX = true;
                if (triplet[1] == target[1]) foundY = true;
                if (triplet[2] == target[2]) foundZ = true;
            }
        }
        return foundX && foundY && foundZ;
    }
}

C++

#include <vector>
using namespace std;

bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
    bool foundX = false, foundY = false, foundZ = false;
    for (auto& triplet : triplets) {
        if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
            if (triplet[0] == target[0]) foundX = true;
            if (triplet[1] == target[1]) foundY = true;
            if (triplet[2] == target[2]) foundZ = true;
        }
    }
    return foundX && foundY && foundZ;
}

JavaScript

function mergeTriplets(triplets, target) {
    let foundX = false, foundY = false, foundZ = false;
    for (let triplet of triplets) {
        if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
            if (triplet[0] == target[0]) foundX = true;
            if (triplet[1] == target[1]) foundY = true;
            if (triplet[2] == target[2]) foundZ = true;
        }
    }
    return foundX && foundY && foundZ;
}

#include <stdlib.h>
#include <stdbool.h>

bool mergeTriplets(int** triplets, int tripletsSize, int* tripletsColSize, int* target, int targetSize) {
    bool foundX = false, foundY = false, foundZ = false;
    
    for (int i = 0; i < tripletsSize; ++i) {
        int *triplet = triplets[i];
        if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
            if (triplet[0] == target[0]) foundX = true;
            if (triplet[1] == target[1]) foundY = true;
            if (triplet[2] == target[2]) foundZ = true;
        }
    }

    return foundX && foundY && foundZ;
}

public class Solution {
    public bool MergeTriplets(int[][] triplets, int[] target) {
        bool foundX = false, foundY = false, foundZ = false;
        foreach(var triplet in triplets) {
            if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
                if (triplet[0] == target[0]) foundX = true;
                if (triplet[1] == target[1]) foundY = true;
                if (triplet[2] == target[2]) foundZ = true;
            }
        }
        return foundX && foundY && foundZ;
    }
}

In Python, similarly manage boolean values to track achievable target elements detectable through hash set equivalents. Such constructs maintain efficiency.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Greedy

Let target = [x, y, z]. We need to determine whether there exists a triplet [a, b, c] such that a leq x, b leq y, and c leq z.

We can divide all triplets into two categories:

Triplets that satisfy a leq x, b leq y, and c leq z.
Triplets that do not satisfy a leq x, b leq y, and c leq z.

For the first category, we can take the maximum values of a, b, and c from these triplets to form a new triplet [d, e, f].

For the second category, we can ignore these triplets because they cannot help us achieve the target triplet.

Finally, we just need to check whether [d, e, f] is equal to target. If it is, return true; otherwise, return false.

Time complexity is O(n), where n is the length of the array triplets. Space complexity is O(1).

TypeScript

function mergeTriplets(triplets: number[][], target: number[]): boolean {
    const [x, y, z] = target;
    let [d, e, f] = [0, 0, 0];
    for (const [a, b, c] of triplets) {
        if (a <= x && b <= y && c <= z) {
            d = Math.max(d, a);
            e = Math.max(e, b);
            f = Math.max(f, c);
        }
    }
    return d === x && e === y && f === z;
}

func mergeTriplets(triplets [][]int, target []int) bool {
	x, y, z := target[0], target[1], target[2]
	d, e, f := 0, 0, 0
	for _, t := range triplets {
		a, b, c := t[0], t[1], t[2]
		if a <= x && b <= y && c <= z {
			d = max(d, a)
			e = max(e, b)
			f = max(f, c)
		}
	}
	return d == x && e == y && f == z
}

Rust

impl Solution {
    pub fn merge_triplets(triplets: Vec<Vec<i32>>, target: Vec<i32>) -> bool {
        let [x, y, z]: [i32; 3] = target.try_into().unwrap();
        let (mut d, mut e, mut f) = (0, 0, 0);

        for triplet in triplets {
            if let [a, b, c] = triplet[..] {
                if a <= x && b <= y && c <= z {
                    d = d.max(a);
                    e = e.max(b);
                    f = f.max(c);
                }
            }
        }

        [d, e, f] == [x, y, z]
    }
}

Scala

object Solution {
    def mergeTriplets(triplets: Array[Array[Int]], target: Array[Int]): Boolean = {
        val Array(x, y, z) = target
        var (d, e, f) = (0, 0, 0)

        for (Array(a, b, c) <- triplets) {
            if (a <= x && b <= y && c <= z) {
                d = d.max(a)
                e = e.max(b)
                f = f.max(c)
            }
        }

        d == x && e == y && f == z
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Filter Valid Triplets and Check Feasibility	Time Complexity: O(n), n being the number of triplets. Space Complexity: O(1).
Hash Set Tracking for Each Target Element	Time Complexity: O(n). Space Complexity: O(1).
Greedy	–

Complexity analysis

Approach	Time	Space	When to Use
Filter Valid Triplets and Check Feasibility (Greedy)	O(n)	O(1)	Best general solution. Efficient single pass with minimal memory.
Hash Set Tracking for Each Target Element	O(n)	O(1)	Useful when you want explicit tracking of satisfied target coordinates.

Frequently asked questions

Is Merge Triplets to Form Target Triplet easy or hard?

Merge Triplets to Form Target Triplet is categorized as a Medium problem on LeetCode. The difficulty comes from recognizing the greedy invariant that triplets exceeding the target must be discarded. Once that observation is made, the implementation becomes a straightforward linear scan.

Merge Triplets to Form Target Triplet Python/Java solution

Python and Java implementations both follow the same greedy logic. Iterate through the list of triplets, skip any triplet that exceeds the target, and track which of the three target values are matched. Once all three are matched, return true. The implementation runs in O(n) time and works identically across Python, Java, C++, and other languages.

How to solve Merge Triplets to Form Target Triplet in O(n)?

Scan the list of triplets once and discard any triplet that contains a value greater than the corresponding target value. For every valid triplet, check if it matches the target value at index 0, 1, or 2 and mark those indices as satisfied. If all three indices become satisfied during the scan, merging those triplets will produce the target triplet. The algorithm uses constant space and linear time.

What is the best approach for Merge Triplets to Form Target Triplet?

The greedy filtering approach is the most efficient and widely expected solution. Iterate through the triplets and ignore any that exceed the target in any coordinate. For the remaining ones, check if they contribute to matching each target index. If all three target values appear across valid triplets, the target can be formed. This runs in O(n) time with O(1) extra space.

Is Merge Triplets to Form Target Triplet asked at Google/Amazon/Meta?

Merge Triplets to Form Target Triplet reflects a common greedy filtering pattern frequently seen in interviews at large tech companies such as Google, Amazon, and Meta. Variants of the problem appear when candidates must eliminate invalid options and combine valid elements to reach a target configuration.

What data structure is used in Merge Triplets to Form Target Triplet?

The core solution primarily uses arrays with simple comparisons. Some implementations also use a small hash set to track which indices of the target triplet have already been satisfied. Since the set size is at most three, the space complexity remains constant.

What is the time complexity of Merge Triplets to Form Target Triplet?

The optimal solution runs in O(n) time where n is the number of triplets. Each triplet is inspected once to verify it does not exceed the target and to check whether it contributes to any target coordinate. Only constant additional space is required because you track at most three flags or indices.

Merge Triplets to Form Target Triplet solution and explanation

The problem

Approach overview

Approach 1: Filter Valid Triplets and Check Feasibility

Approach 2: Hash Set Tracking for Each Target Element

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Merge Triplets to Form Target Triplet solution and explanation

The problem

Approach overview

Approach 1: Filter Valid Triplets and Check Feasibility

Approach 2: Hash Set Tracking for Each Target Element

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems