A paint mixer stores colours as triples [r, g, b]. You start with a list of triples, and you may repeat this step as often as you like (including zero times):
- pick two different positions
iandj, and overwritetriples[j]with the element-wise maximum of the two:[max(r_i, r_j), max(g_i, g_j), max(b_i, b_j)].
Write can_reach_target(triples: list[list[int]], target: list[int]) -> bool that returns True if you can make target appear as one of the triples in the list.
can_reach_target([[2, 5, 3], [1, 8, 4], [1, 7, 5]], [2, 7, 5]) # True mix [2, 5, 3] into [1, 7, 5]
can_reach_target([[3, 4, 5], [4, 5, 6]], [3, 2, 5]) # False nothing has a 2 in the middle
can_reach_target([[2, 5, 3], [2, 3, 4], [1, 2, 5], [5, 2, 3]], [5, 5, 5]) # True
can_reach_target([[4, 4, 4]], [4, 4, 4]) # True already there
Constraints:
1 <= len(triples) <= 10^5, every triple andtargethave length 3- all values are between
1and1000
Trying different orders of mixing blows up quickly. Aim for O(n) time and O(1) extra space.
Show hint
a mix can only raise values, never lower them. What does that tell you about a triple that has any value above the target's?