Merge Triplets to Form Target Triplet

Med

#1733Time: O(N), where N is the number of triplets. The first loop for filtering takes O(N) time. The second loop for merging takes O(M) time, where M is the number of good triplets (M <= N). So the total time complexity is O(N).Space: O(M) or O(N) in the worst case, for storing the `goodTriplets` list, where N is the total number of triplets and M is the number of good triplets. In the worst case, all triplets are "good", so we need space proportional to the input size.

Patterns

Greedy

Data structures

Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first filters the input triplets to keep only those that could potentially contribute to forming the target triplet. A triplet is a potential candidate only if each of its elements is less than or equal to the corresponding element in the target. After filtering, it merges all these candidate triplets to see if the final result matches the target.

Algorithm

1. Create an empty list, goodTriplets.
1. Iterate through each triplet in the input triplets.
1. If triplet[0] <= target[0] AND triplet[1] <= target[1] AND triplet[2] <= target[2], add triplet to goodTriplets.
1. Initialize a result triplet res = [0, 0, 0].
1. Iterate through each goodTriplet in goodTriplets.
1. Update res: res[0] = max(res[0], goodTriplet[0]), res[1] = max(res[1], goodTriplet[1]), res[2] = max(res[2], goodTriplet[2]).
1. Return true if res is equal to target, otherwise return false.

Walkthrough

The core idea is based on the property of the max operation. When we merge triplets, the values in the resulting triplet can only increase or stay the same. Therefore, any triplet that has an element greater than the corresponding element in the target triplet can never be part of a merge that results in the target. Such triplets are "invalid" and can be discarded. The algorithm proceeds in two main phases:

Filtering Phase: Iterate through the original triplets array. Create a new list of "good" triplets, containing only those [a, b, c] for which a <= target[0], b <= target[1], and c <= target[2].
Merging Phase: If the list of good triplets is not empty, we can effectively merge all of them. The result of merging all good triplets would be a triplet [max_a, max_b, max_c], where max_a is the maximum of all first elements of the good triplets, and so on. We can find these maximums by iterating through the list of good triplets.
Verification: Finally, we check if this [max_a, max_b, max_c] is equal to the target triplet. If they are equal, it means we can form the target; otherwise, we cannot.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean mergeTriplets(int[][] triplets, int[] target) {6        List<int[]> goodTriplets = new ArrayList<>();7        for (int[] t : triplets) {8            if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {9                goodTriplets.add(t);10            }11        }12 13        int[] res = {0, 0, 0};14        for (int[] t : goodTriplets) {15            res[0] = Math.max(res[0], t[0]);16            res[1] = Math.max(res[1], t[1]);17            res[2] = Math.max(res[2], t[2]);18        }19 20        return res[0] == target[0] && res[1] == target[1] && res[2] == target[2];21    }22}

Complexity

Time

O(N), where N is the number of triplets. The first loop for filtering takes O(N) time. The second loop for merging takes O(M) time, where M is the number of good triplets (M <= N). So the total time complexity is O(N).

Space

O(M) or O(N) in the worst case, for storing the `goodTriplets` list, where N is the total number of triplets and M is the number of good triplets. In the worst case, all triplets are "good", so we need space proportional to the input size.

Trade-offs

Pros

Correctly solves the problem.
The logic is straightforward and easy to understand: filter then process.

Cons

Uses extra space to store the filtered triplets, which can be significant if the input array is large.

This is an optimized version of the greedy approach that uses a single pass over the input array and constant extra space. It identifies valid triplets and simultaneously checks if the necessary components to form the target (x, y, and z) have been found among these valid triplets.

Algorithm

1. Initialize three boolean flags: foundX = false, foundY = false, foundZ = false.
1. Let target = [x, y, z].
1. Iterate through each triplet = [a, b, c] in the input triplets.
1. Check if the triplet is "good": a <= x AND b <= y AND c <= z.
1. If it is a good triplet:
- If a == x, set foundX = true.
- If b == y, set foundY = true.
- If c == z, set foundZ = true.
1. After the loop, return foundX && foundY && foundZ.

Walkthrough

This approach builds upon the same key insight: any triplet with an element larger than the corresponding target element is useless. However, instead of storing all "good" triplets, we can process them on the fly. We need to find if it's possible to construct the target = [x, y, z]. This requires three things to be true simultaneously:

There exists a good triplet [x, b, c] (where b <= y, c <= z).
There exists a good triplet [a, y, c] (where a <= x, c <= z).
There exists a good triplet [a, b, z] (where a <= x, b <= y). Note that these could be the same triplet or different triplets. By merging them, we can achieve the target. For example, merging [x, b1, c1], [a2, y, c2], and [a3, b3, z] (all good) results in [max(x, a2, a3), max(b1, y, b3), max(c1, c2, z)] which simplifies to [x, y, z] because all a_i <= x, b_i <= y, c_i <= z. So, the problem reduces to checking if we can find a good triplet that matches the x component, a good one that matches the y component, and a good one that matches the z component. We can track this using three boolean flags. We iterate through the triplets once. For each triplet, we first check if it's "good". If it is, we then check if any of its components match the corresponding target components and update our flags accordingly.

1class Solution {2    public boolean mergeTriplets(int[][] triplets, int[] target) {3        boolean foundX = false;4        boolean foundY = false;5        boolean foundZ = false;6 7        int targetX = target[0];8        int targetY = target[1];9        int targetZ = target[2];10 11        for (int[] triplet : triplets) {12            // This is a "good" triplet if no element exceeds the corresponding target element.13            if (triplet[0] <= targetX && triplet[1] <= targetY && triplet[2] <= targetZ) {14                // Check if this triplet helps us match any of the target's components.15                if (triplet[0] == targetX) {16                    foundX = true;17                }18                if (triplet[1] == targetY) {19                    foundY = true;20                }21                if (triplet[2] == targetZ) {22                    foundZ = true;23                }24            }25        }26 27        return foundX && foundY && foundZ;28    }29}

Complexity

Time

O(N), where N is the number of triplets. We iterate through the `triplets` array only once.

Space

O(1). We only use a few boolean variables to track the state, regardless of the input size.

Trade-offs

Pros

Highly efficient in both time and space.
Solves the problem in a single pass.

Cons

The logic might be slightly less intuitive at first glance compared to the two-pass approach, as it combines filtering and checking in one step.

Solutions

Solution

1class Solution {2public3  boolean mergeTriplets(int[][] triplets, int[] target) {4    int x = target[0], y = target[1], z = target[2];5    int d = 0, e = 0, f = 0;6    for (var t : triplets) {7      int a = t[0], b = t[1], c = t[2];8      if (a <= x && b <= y && c <= z) {9        d = Math.max(d, a);10        e = Math.max(e, b);11        f = Math.max(f, c);12      }13    }14    return d == x && e == y && f == z;15  }16}

1class Solution {2public:3  bool mergeTriplets(vector<vector<int>> &triplets, vector<int> &target) {4    int x = target[0], y = target[1], z = target[2];5    int d = 0, e = 0, f = 0;6    for (auto &t : triplets) {7      int a = t[0], b = t[1], c = t[2];8      if (a <= x && b <= y && c <= z) {9        d = max(d, a);10        e = max(e, b);11        f = max(f, c);12      }13    }14    return d == x && e == y && f == z;15  }16};

1class Solution:2    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool: x, y, z = target d = e = f = 0 for a, b, c in triplets: if a <= x and b <= y and c <= z: d = max(d, a) e = max(e, b) f = max(f, c) return [d, e, f] == target

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem