# Merge Triplets to Form Target Triplet
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/merge-triplets-to-form-target-triplet)
Canonical: https://scaleengineer.com/dsa/problems/merge-triplets-to-form-target-triplet
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Greedy Two-Pass with Filtering
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.
**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.
**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.
### Explanation
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:
1.  **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]`.
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.
3.  **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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        List<int[]> goodTriplets = new ArrayList<>();
        for (int[] t : triplets) {
            if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
                goodTriplets.add(t);
            }
        }

        int[] res = {0, 0, 0};
        for (int[] t : goodTriplets) {
            res[0] = Math.max(res[0], t[0]);
            res[1] = Math.max(res[1], t[1]);
            res[2] = Math.max(res[2], t[2]);
        }

        return res[0] == target[0] && res[1] == target[1] && res[2] == target[2];
    }
}
```
### Algorithm
- 1. Create an empty list, `goodTriplets`.
- 2. Iterate through each `triplet` in the input `triplets`.
- 3. If `triplet[0] <= target[0]` AND `triplet[1] <= target[1]` AND `triplet[2] <= target[2]`, add `triplet` to `goodTriplets`.
- 4. Initialize a result triplet `res = [0, 0, 0]`.
- 5. Iterate through each `goodTriplet` in `goodTriplets`.
- 6. Update `res`: `res[0] = max(res[0], goodTriplet[0])`, `res[1] = max(res[1], goodTriplet[1])`, `res[2] = max(res[2], goodTriplet[2])`.
- 7. Return `true` if `res` is equal to `target`, otherwise return `false`.

## Greedy Single-Pass Check
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.
**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.
**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.
### Explanation
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:
1. There exists a good triplet `[x, b, c]` (where `b <= y`, `c <= z`).
2. There exists a good triplet `[a, y, c]` (where `a <= x`, `c <= z`).
3. 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.

```java
class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean foundX = false;
        boolean foundY = false;
        boolean foundZ = false;

        int targetX = target[0];
        int targetY = target[1];
        int targetZ = target[2];

        for (int[] triplet : triplets) {
            // This is a "good" triplet if no element exceeds the corresponding target element.
            if (triplet[0] <= targetX && triplet[1] <= targetY && triplet[2] <= targetZ) {
                // Check if this triplet helps us match any of the target's components.
                if (triplet[0] == targetX) {
                    foundX = true;
                }
                if (triplet[1] == targetY) {
                    foundY = true;
                }
                if (triplet[2] == targetZ) {
                    foundZ = true;
                }
            }
        }

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

# Solutions
### Java

```java
class Solution {
public
  boolean mergeTriplets(int[][] triplets, int[] target) {
    int x = target[0], y = target[1], z = target[2];
    int d = 0, e = 0, f = 0;
    for (var t : triplets) {
      int a = t[0], b = t[1], c = t[2];
      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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool mergeTriplets(vector<vector<int>> &triplets, vector<int> &target) {
    int x = target[0], y = target[1], z = target[2];
    int d = 0, e = 0, f = 0;
    for (auto &t : triplets) {
      int a = t[0], b = t[1], c = 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;
  }
};

```

### Python

```python
class Solution:
    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

```