1899. Merge Triplets to Form Target Triplet

Description

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

Solutions

Solution 1: Greedy

Let \(\textit{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 \(\textit{target}\). If it is, return \(\textit{true}\); otherwise, return \(\textit{false}\).

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

Python3JavaC++GoTypeScriptRustScala

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

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;
    }
}

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;
    }
};

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
}

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;
}

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]
    }
}

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
    }
}

Comments