Merge Triplets to Form Target Triplet

MediumGreedygreedy

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a list of integer triplets triplets and a target triplet [x, y, z]. A merge picks two triplets i != j and replaces triplets[j] with the element-wise maximum of the two: [max(a1,a2), max(b1,b2), max(c1,c2)]. You may perform any number of merges, including none. Return true if, after some sequence of merges, target appears as one of the triplets, and false otherwise.

Examples

Input: triplets = [[1,4,2],[3,1,5],[2,6,1]], target = [3,4,5]
Output: true
Merging [1,4,2] and [3,1,5] gives [3,4,5]. [2,6,1] is never used because its 6 would overshoot.
Input: triplets = [[2,2,2],[1,3,1]], target = [2,3,3]
Output: false
No triplet has 3 in the last position.

Constraints

  • 1 <= triplets.length <= 10^5
  • `triplets[i].length == target.length == 3`
  • 1 <= values <= 1000

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More greedy problems