#1899

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Merge Triplets to Form Target Triplet

Determine if target triplet can be formed by merging given triplets using greedy selection and invariant checks.

Problem Statement

You are given a 2D integer array triplets where each triplet represents [ai, bi, ci], and a target triplet [x, y, z]. You can merge two triplets by taking the maximum of each corresponding element.

Return true if it is possible to obtain the target triplet as one of the elements of triplets by performing any number of merges, otherwise return false. Each merge must maintain the invariant that no element exceeds the corresponding target value.

Examples

Example 1

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

Output: true

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

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

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

Solution Approach

Filter Valid Triplets

Ignore any triplet that has an element greater than the corresponding target value, because merging it would exceed the target. This reduces unnecessary computation and focuses on achievable combinations.

Track Maximums Greedily

For each remaining triplet, update a running maximum for each position. If the running maximum matches the target triplet after processing all valid triplets, the target can be formed. This exploits the greedy pattern of choosing the best current option for each dimension.

Verify Target Match

After updating maximums for all valid triplets, compare the running maximum array to the target triplet. Return true if all elements match, otherwise return false. This step ensures the invariant that no dimension exceeds the target.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each triplet is processed once. Space complexity is O(1) beyond input storage, using only three variables to track running maximums.

What Interviewers Usually Probe

Candidate considers which triplets actually affect the target values.
Candidate identifies unnecessary merges that violate the target invariant.
Candidate uses a greedy update to track max values efficiently.

Common Pitfalls or Variants

Common pitfalls

Including triplets with elements exceeding the target, which breaks the invariant.
Failing to track all three dimensions correctly, leading to false negatives.
Attempting all merge permutations instead of using greedy selection.

Follow-up variants

Target triplet size larger than 3, generalizing the greedy merge approach.
Triplets contain negative numbers, requiring careful maximum computation.
Return the minimum number of merges needed instead of a boolean result.

FAQ

What is the main pattern in Merge Triplets to Form Target Triplet?

The primary pattern is greedy selection combined with invariant validation to ensure no dimension exceeds the target while merging.

Why do we ignore triplets exceeding the target?

Triplets with elements larger than the target cannot contribute to forming the target without violating the invariant, so they are discarded.

Can we merge triplets in any order?

Yes, but the greedy approach ensures we only track the maximum in each position, simplifying the process and avoiding unnecessary merges.

What is the time complexity of this solution?

The solution runs in O(n) time since each triplet is processed once for comparison and maximum updates.

How do we handle multiple valid merge sequences?

All valid sequences converge to the same running maximums, so the algorithm only needs to consider valid triplets once, ignoring merge order.

terminal

Solution

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$.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#1877 minimize maximum pair sum in array #1921 eliminate maximum number of monsters #1936 add minimum number of rungs