209. Blend to Target
A paint shop stores recipes as triplets [a, b, c]: the amount of red, green and blue in a colour. You may blend two recipes, say recipe x and recipe y, which replaces recipe y with [max(ax, ay), max(bx, by), max(cx, cy)], taking the larger amount of each pigment. Recipe x stays as it was. You may blend as many times as you like, in any order.
Given the list triplets and a target = [x, y, z], return true if the target recipe can appear in the list after some number of blends (possibly zero), and false otherwise.
Example 1
- Input:
- triplets = [[3,1,2],[4,6,1],[2,9,8],[3,5,5]]target = [4,6,5]
- Output:
- true
- Explanation:
The recipe [2,9,8] has a pigment above the target (9 > 6), so it is useless. Blending [3,1,2], [4,6,1] and [3,5,5] gives [4,6,5], the target.
Example 2
- Input:
- triplets = [[5,5,5],[1,1,1]], target = [4,4,4]
- Output:
- false
- Explanation:
[5,5,5] exceeds the target in every pigment, so only [1,1,1] can be used, and blending never raises anything above 1.
Example 3
- Input:
- triplets = [[2,3,4]], target = [2,3,4]
- Output:
- true
- Explanation:
The target is already in the list.
Constraints
1 ≤ triplets.length ≤ 105
1 ≤ a, b, c, x, y, z ≤ 109
triplets[i].length == 3, target.length == 3
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)