Blend to the Target Mix
MediumGreedy
Problem
A paint shop stores colour recipes as triples [r, g, b]. A blend takes two stored triples and overwrites one of them with their component-wise maximum: [max(r1, r2), max(g1, g2), max(b1, b2)]. You may blend any number of times.
Return true if some stored triple can be made exactly equal to target, false otherwise.
Example 1
- Input:
- triplets = [[2, 5, 3], [1, 8, 4], [1, 7, 5]], target = [2, 7, 5]
- Output:
- true
Blend [2, 5, 3] with [1, 7, 5] to get [2, 7, 5]. [1, 8, 4] must be avoided because its 8 overshoots.
Example 2
- Input:
- triplets = [[3, 4, 5], [4, 5, 6]], target = [3, 2, 5]
- Output:
- false
Every triple has a green value above 2, and blending can only raise values.
Constraints
- 1 ≤ triplets.length ≤ 10^5
- 1 ≤ every value ≤ 1000
- target has 3 values
Hint
Show the first hint
Blending can only increase values. What does that say about a triple with any value above the target?
Walkthrough
How to approach it
01Clarify before coding
- Do blends destroy the other triple? No, only one triple is overwritten; the other is unchanged, but that does not matter for reachability.
- Must the result be exactly the target? Yes, equal in all three components.
- Can a stored triple already equal the target? Yes, that counts.
02Brute force
Try every subset of triples, compute its component-wise max and compare with the target.
Cost: O(2^n): impossible for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.