Merge Triplets to Form Target Triplet

Medium Subject: Greedy

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

Problem Statement

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]. You can perform the following operation any number of times: Choose two indexes i and j and update triplets[j] to [max(ai, aj), max(bi, bj), max(ci, cj)]. Return true if it is possible to obtain the target triplet.

Example 1:

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true

Optimal Solution

Python

Approach: Filter and Maximize

We can only form the target if we use triplets whose values are all less than or equal to the target's values. We filter out invalid triplets. Then, we check if the element-wise maximum of the remaining valid triplets equals the target.

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        x = y = z = False

        for t in triplets:
            if t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]:
                x = x or (t[0] == target[0])
                y = y or (t[1] == target[1])
                z = z or (t[2] == target[2])

        return x and y and z