All problems

Merge Triplets to Form Target Triplet

Medium · greedy

You are given a list triplets, where each triplet is three integers [a, b, c], and a target triplet [x, y, z].

You may choose any group of triplets from the list (at least one, each triplet used at most once) and merge them into a single triplet: position by position, the merged triplet keeps the largest value found at that position among the chosen triplets. For example, merging [2, 5, 1] and [4, 3, 3] gives [4, 5, 3].

Return true if some group of triplets merges into exactly target, and false otherwise.

Examples

Example 1

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

Output: true

Merge the first and third triplets: the largest values by position are 2, 7 and 5. The second triplet has an 8, which would overshoot, so it is not used.

Example 2

Input: triplets = [[3, 4, 5], [4, 5, 6]], target = [3, 2, 5]

Output: false

The second position of the target is 2, but every triplet has a value of at least 4 there.

Example 3

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

Output: true

Merge the first, third and fourth triplets to get [5, 5, 5].

Constraints