Merge Triplets to Form Target Triplet

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.

Examples

Example 1:

1
2
3
4
5
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:

1
2
3
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:

1
2
3
4
5
6
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.

Solution

Method 1 – Greedy Filtering and Merging

Intuition

The key idea is to only consider triplets where each value does not exceed the corresponding value in the target. By greedily merging these valid triplets, we can maximize each dimension and try to reach the target. If we can form the target triplet by combining these, the answer is true.

Approach

Initialize a result triplet ans as [0, 0, 0].
Iterate through each triplet in the input:
- If all elements of the triplet are less than or equal to the corresponding elements in the target, consider it valid.
- For each valid triplet, update ans by taking the maximum of each coordinate with the current triplet.
After processing all triplets, check if ans matches the target triplet.
Return true if they match, false otherwise.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
     bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& t) {
          vector<int> ans(3, 0);
          for (auto& s : triplets) {
                if (s[0] <= t[0] && s[1] <= t[1] && s[2] <= t[2]) {
                     ans[0] = max(ans[0], s[0]);
                     ans[1] = max(ans[1], s[1]);
                     ans[2] = max(ans[2], s[2]);
                }
          }
          return ans == t;
     }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func mergeTriplets(triplets [][]int, t []int) bool {
     ans := []int{0, 0, 0}
     for _, s := range triplets {
          if s[0] <= t[0] && s[1] <= t[1] && s[2] <= t[2] {
                if s[0] > ans[0] { ans[0] = s[0] }
                if s[1] > ans[1] { ans[1] = s[1] }
                if s[2] > ans[2] { ans[2] = s[2] }
          }
     }
     return ans[0] == t[0] && ans[1] == t[1] && ans[2] == t[2]
}

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] t) {
        int[] ans = new int[3];
        for (var s : triplets)
            if (s[0] <= t[0] && s[1] <= t[1] && s[2] <= t[2])
                ans = new int[]{ Math.max(ans[0], s[0]), Math.max(ans[1], s[1]), Math.max(ans[2], s[2]) };
        return Arrays.equals(ans, t);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
     fun mergeTriplets(triplets: Array<IntArray>, t: IntArray): Boolean {
          val ans = IntArray(3)
          for (s in triplets) {
                if (s[0] <= t[0] && s[1] <= t[1] && s[2] <= t[2]) {
                     ans[0] = maxOf(ans[0], s[0])
                     ans[1] = maxOf(ans[1], s[1])
                     ans[2] = maxOf(ans[2], s[2])
                }
          }
          return ans.contentEquals(t)
     }
}

1
2
3
4
5
6
7
8
9
class Solution:
     def mergeTriplets(self, triplets: list[list[int]], t: list[int]) -> bool:
          ans = [0, 0, 0]
          for s in triplets:
                if s[0] <= t[0] and s[1] <= t[1] and s[2] <= t[2]:
                     ans[0] = max(ans[0], s[0])
                     ans[1] = max(ans[1], s[1])
                     ans[2] = max(ans[2], s[2])
          return ans == t

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
     pub fn merge_triplets(triplets: Vec<Vec<i32>>, t: Vec<i32>) -> bool {
          let mut ans = vec![0, 0, 0];
          for s in triplets.iter() {
                if s[0] <= t[0] && s[1] <= t[1] && s[2] <= t[2] {
                     ans[0] = ans[0].max(s[0]);
                     ans[1] = ans[1].max(s[1]);
                     ans[2] = ans[2].max(s[2]);
                }
          }
          ans == t
     }
}

Complexity

⏰ Time complexity: O(N), where N is the number of triplets.
🧺 Space complexity: O(1), as only a fixed-size array is used.

Problem#

Examples#

Solution#

Method 1 – Greedy Filtering and Merging#

Intuition#

Approach#

Code#

Complexity#