target · a slot lights up once a safe triplet matches it
triplets
public boolean mergeTriplets(int[][] triplets, int[] target) { Set<Integer> good = new HashSet<>(); // slots hit exactly for (int[] t : triplets) { if (t[0] > target[0] || t[1] > target[1] || t[2] > target[2]) { continue; // would overshoot forever } for (int i = 0; i < 3; i++) { if (t[i] == target[i]) { good.add(i); } } } return good.size() == 3;}
- t
- —
- target
- —
- good
- {}
- kept
- 0
Why it works
- Brute force tries every subset of triplets, merges it and compares with the target: O(2ⁿ).
- A merge can only grow values. So any triplet with a slot above the target poisons every merge it joins: that slot can never come back down. Drop it.
- Merging all the safe triplets is the best you can do. None of them overshoots, so their merge stays ≤ target in each slot. It equals the target exactly when every slot is matched by at least one safe triplet, which is what
goodtracks. One pass, O(n) time, O(1) space. - Pitfall: matching a slot is not enough on its own; check the filter first. In
[3,3,9]with target[3,3,1], both 3s match but the 9 overshoots, so neither may count. - Pattern: "filter out what can never be undone, then greedily take everything else". The same thinking fits problems where an operation only increases (max, OR) or only decreases (min, AND).