Skip to main content
Talentd

Merge Triplets to Form Target Triplet - Solution & Explanation

MediumArrayGreedy23 min readAsked at: Google
Practice this problem

Problem Statement

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith 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(ai, aj), max(bi, bj), max(ci, cj)].
    • 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 <= 105
  • triplets[i].length == target.length == 3
  • 1 <= ai, bi, ci, 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.

The function mergeTriplets iterates over each triplet, checking if each element is less than or equal to the corresponding target element. If valid, it updates canAchieve array to true where the triplet matches the target.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the size of the input triplets.
Space Complexity: O(1), as we only use a constant amount of space.

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.

This alternative C solution employs three boolean flags (foundX, foundY, foundZ) to denote if each element of the target can be built from eligible triplets. This aligns with the hash set concept but is adaptive to C's capabilities.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), with n being the count of triplets.
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:

  1. Triplets that satisfy a leq x, b leq y, and c leq z.
  2. 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).

Code

PythonJavaC++GoTypeScriptRustScala

Python

Java

C++

Go

TypeScript

Rust

Scala

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Filter Valid Triplets and Check Feasibility

Time Complexity: O(n), where n is the size of the input triplets.
Space Complexity: O(1), as we only use a constant amount of space.

Hash Set Tracking for Each Target Element

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

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 ElementO(n)O(1)Useful when you want explicit tracking of satisfied target coordinates.

Video Solution

Merge Triplets to Form Target Triplet - Greedy - Leetcode 1899 - Python • NeetCode • 46,105 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Merge Triplets to Form Target Triplet with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays