Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1899.html

1899. Merge Triplets to Form Target Triplet

Level

Medium

Description

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, 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 = [[1,3,4],[2,5,8]], target = [2,5,8]

Output: true

Explanation: The target triplet [2,5,8] is already an element of 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.

Example 4:

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.

Constraints:

  • 1 <= triplets.length <= 10^5
  • triplets[i].length == target.length == 3
  • 1 <= a_i, b_i, c_i, x, y, z <= 1000

Solution

Create an array merged of length 3 to store the merged triplet, where all elements in merged are 0 initially. Loop over triplets. For each triplet in triplets, if all the elements in triplet are less than the corresponding elements in target, then merge triplet to merged. Finally, check whether merged and target are equal.

  • class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        int[] merged = new int[3];
        for (int[] triplet : triplets) {
            if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
                merged[0] = Math.max(merged[0], triplet[0]);
                merged[1] = Math.max(merged[1], triplet[1]);
                merged[2] = Math.max(merged[2], triplet[2]);
            }
        }
        return Arrays.equals(merged, target);
    }
}

############

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        int maxA = 0, maxB = 0, maxC = 0;
        for (int[] triplet : triplets) {
            int a = triplet[0], b = triplet[1], c = triplet[2];
            if (a <= target[0] && b <= target[1] && c <= target[2]) {
                maxA = Math.max(maxA, a);
                maxB = Math.max(maxB, b);
                maxC = Math.max(maxC, c);
            }
        }
        return maxA == target[0] && maxB == target[1] && maxC == target[2];
    }
}

  • // OJ: https://leetcode.com/problems/merge-triplets-to-form-target-triplet/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& A, vector<int>& T) {
        int cnt[3] = {};
        for (int i = 0; i < A.size(); ++i) {
            if (A[i][0] > T[0] || A[i][1] > T[1] || A[i][2] > T[2]) continue;
            for (int t = 0; t < 3; ++t)
                if (A[i][t] == T[t]) cnt[t] = 1;
        }
        for (int t = 0; t < 3; ++t) {
            if (cnt[t] == 0) return false;
        }
        return true;
    }
};

  • class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        maxA = maxB = maxC = 0
        tA, tB, tC = target
        for a, b, c in triplets:
            if a <= tA and b <= tB and c <= tC:
                maxA = max(maxA, a)
                maxB = max(maxB, b)
                maxC = max(maxC, c)
        return (maxA, maxB, maxC) == (tA, tB, tC)

############

# 1899. Merge Triplets to Form Target Triplet
# https://leetcode.com/problems/merge-triplets-to-form-target-triplet

class Solution:
    def mergeTriplets(self, t: List[List[int]], target: List[int]) -> bool:
        res = [False] * 3
        
        for a,b,c in t:            
            if a == target[0] and b <= target[1] and c <= target[2]: 
                res[0] = True
            if b == target[1] and a <= target[0] and c <= target[2]: 
                res[1] = True
            if c == target[2] and b <= target[1] and a <= target[0]: 
                res[2] = True
                
        return all(res)


  • function mergeTriplets(triplets: number[][], target: number[]): boolean {
    let [x, y, z] = target; // 目标值
    let [i, j, k] = [0, 0, 0]; // 最大值
    for (let triplet of triplets) {
        let [a, b, c] = triplet; // 当前值
        if (a <= x && b <= y && c <= z) {
            i = Math.max(i, a);
            j = Math.max(j, b);
            k = Math.max(k, c);
        }
    }
    return i == x && j == y && k == 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
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

All Problems

All Solutions