LeetMotion
You are given a list of triplets triplets[i] = [a, b, c] and a target = [x, y, z]. You can merge any two triplets by taking the element-wise maximum. Return true if some sequence of merges can produce exactly target as one of the triplets.
1 ≤ triplets.length ≤ 10001 ≤ a, b, c, x, y, z ≤ 100The operation is element-wise maximum — values can only increase when merging. This gives us an immediate filter: any triplet with a value exceeding the target at any position is permanently useless. Including it would push that position above the target, which can never be undone.
After filtering, the question simplifies beautifully: do the remaining triplets collectively cover all three target positions? That is, does some valid triplet match target[0], some valid triplet match target[1], and some valid triplet match target[2]? They don't need to be the same triplet. Merging independently-contributing triplets produces exactly the target.
Maintain a set good tracking which target positions (0, 1, 2) have been covered. For each triplet, skip it if any value exceeds the target. Otherwise, for each index where the triplet's value equals the target, add that index to good. Return len(good) == 3.
def mergeTriplets(triplets, target):
good = set()
for t in triplets:
if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
continue # would push a value above target
for i, v in enumerate(t):
if v == target[i]:
good.add(i) # this triplet contributes position i
return len(good) == 3Same logic, but use three boolean flags instead of a set. Each flag tracks whether a specific target position can be satisfied. Because the set has constant size ≤ 3, both approaches are technically O(1) space — but flags make the intent even clearer.
def mergeTriplets(triplets, target):
x = y = z = False
for t in triplets:
x |= (t[0] == target[0] and t[1] <= target[1] and t[2] <= target[2])
y |= (t[0] <= target[0] and t[1] == target[1] and t[2] <= target[2])
z |= (t[0] <= target[0] and t[1] <= target[1] and t[2] == target[2])
if x and y and z:
return True
return FalseNote the subtle difference: to set flag x, the triplet must match target[0] and not exceed target[1] or target[2]. This is equivalent to the filter in approach 1 — a triplet that exceeds any target position cannot be used at all.
| Approach | Time | Space | Notes |
|---|---|---|---|
| Set-based | O(n) | O(1) | Clearest to read |
| Boolean flags | O(n) | O(1) | Early exit possible |
This is a filter + coverage greedy. It appears in problems where:
max(a, max(b, c)) = max(max(a, b), c) — element-wise max is associative and commutative. So the result of merging a set of triplets is always the same regardless of the order you merge them. This means: if you can find one triplet contributing x and another contributing y and another contributing z, merging all three in any order gives target.
If triplet t has t[j] > target[j] for any j, then merging t into any result will set position j to at least t[j] > target[j]. Since we can't decrease values, the target can never be reached if t is included. Skipping it is mandatory. Conversely, for any triplet that doesn't exceed the target anywhere, including it in the merge can only bring values closer to the target (or leave them unchanged).
This is the #1 mistake. A triplet like [5, 10, 3] with target = [5, 4, 3] looks useful (it matches positions 0 and 2), but merging it would set position 1 to at least 10, blowing past target[1] = 4. It must be skipped entirely.
You don't. The target can be assembled from up to three different triplets, each contributing one position. The merge operation combines them.
good = {0, 1} means positions 0 and 1 are satisfied but position 2 is not. Return false — you need all three.
triplets=[[1,1,1]], target=[1,1,1] → true (exact match)triplets=[[2,1,1]], target=[1,1,1] → false (t[0]=2 > target[0]=1, skip)triplets=[[1,2,3],[3,1,1]], target=[3,2,3] → true ([1,2,3] covers y,z; [3,1,1] covers x)triplets=[[1,1,2]], target=[1,1,1] → false (t[2]=2 > 1, skip; nothing left)
Discussion
…