LeetCode 1899 · Greedy · concept: greedy
Problem
Merging two triplets replaces each with the element-wise max. Given triplets and a target, can repeated merges produce exactly target?
Approach — keep only “safe” triplets, check coverage (optimal)
Since merging takes element-wise maxima, any triplet with some component larger than the target’s would push that component too high forever — it’s unusable. Discard those. Among the safe triplets (all components ≤ target), you just need each target position i to be achievable: some safe triplet whose i-th value equals target[i].
def mergeTriplets(triplets, target):
matched = set() # which target positions are hit exactly
for t in triplets:
if t[0] <= target[0] and t[1] <= target[1] and t[2] <= target[2]: # safe
for i in range(3):
if t[i] == target[i]:
matched.add(i)
return len(matched) == 3Time O(n), space O(1).
Why “safe + each position matched” suffices
A triplet exceeding the target in any component can never be merged in (max is monotonic — it would overshoot permanently), so it’s out. Merging all the safe triplets together takes the max per position; if every position i has at least one safe triplet hitting target[i] exactly, the combined max equals the target. Merging all safe ones is harmless because none exceeds the target anywhere.
Key insight
Element-wise-max merges → discard anything that would overshoot, then check each coordinate is achievable. The greedy realization “an over-target component is permanently disqualifying” filters the input, after which the answer is a simple per-position coverage check.
Related
- concept: greedy
- prev: Hand of Straights · next: Partition Labels
Software engineering
Infrastructure & security
Computer science
Hardware & engineering