Merge Triplets to Form Target Triplet

Medium · Greedy

You are given a list of triplets, each containing three integers, and a separate target triplet. You may combine any subset of the triplets using an element-wise maximum operation (repeatedly replacing two triplets with a new one whose i-th value is the max of their i-th values). Determine whether it is possible to produce the exact target triplet this way. Return true if it can be done, false otherwise.

Examples

Input:  triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Why:    Merging [2,5,3] and [1,7,5] gives [2,7,5] which matches the target.

Input:  triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Why:    Both triplets have a value exceeding the target in some position, so combining them never stays within bounds and matches.

Input:  triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Why:    Combining [2,5,3], [1,2,5], and [5,2,3] yields [5,5,5].

Constraints

1 <= triplets.length <= 10^5, triplets[i].length == target.length == 3, 1 <= triplets[i][j], target[j] <= 1000

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Merge Triplets to Form Target Triplet

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Merge Triplets to Form Target Triplet. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.