Merge Triplets to Target LeetCode 1899

LeetCode 1899 — Merge Triplets to Form Target Triplet — gives you a 2D array triplets where each triplet is [a, b, c], and a target triplet [x, y, z]. You can merge any number of triplets by taking the element-wise maximum. Return true if you can form the target triplet.

Merging means: if you merge [a1, b1, c1] and [a2, b2, c2], the result is [max(a1,a2), max(b1,b2), max(c1,c2)]. You can merge any subset of the given triplets. The question is whether some subset produces exactly [x, y, z].

The greedy insight is elegant: since merging only takes maximums, including a triplet where any element exceeds the target is fatal — it would push that position above the target permanently. Filter those out, then check if the remaining triplets can cover all three target values.

Step 1: filter out every triplet where a > x, b > y, or c > z. Any such triplet, if included in the merge, would push the result above the target at that position. Since max is monotonic, there is no way to "undo" an oversized value.

Step 2: from the remaining valid triplets, check if there exists at least one triplet with a == x (to provide the target's first value), at least one with b == y, and at least one with c == z. These do not need to be the same triplet — merging brings all three to their max.

If all three target values are achievable from the valid set, return true. Otherwise return false. This two-step process runs in O(n) time with a single pass through the triplets.

The filter and check can be combined into one loop. Initialize three booleans: foundX = foundY = foundZ = false. For each triplet [a, b, c], if a <= x and b <= y and c <= z (the triplet is valid), then check: if a == x set foundX = true, if b == y set foundY = true, if c == z set foundZ = true.

After processing all triplets, return foundX and foundY and foundZ. This single pass eliminates the need for a separate filtering step and uses O(1) extra space.

The correctness follows from the merge operation: if foundX, foundY, and foundZ are all true, there exist valid triplets that achieve each target value. Merging all valid triplets together produces a result where each position is at least the target value (since we found exact matches) and at most the target value (since we filtered oversized ones).

Consider triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]. Process each triplet: [2,5,3]: 2<=2, 5<=7, 3<=5 — valid. a==2 → foundX=true. b=5≠7. c=3≠5. [1,8,4]: b=8 > 7 — invalid, skip.

[1,7,5]: 1<=2, 7<=7, 5<=5 — valid. a=1≠2. b==7 → foundY=true. c==5 → foundZ=true. Result: foundX=true, foundY=true, foundZ=true → return true.

Verification: merge [2,5,3] and [1,7,5] → [max(2,1), max(5,7), max(3,5)] = [2,7,5] = target. The invalid triplet [1,8,4] was correctly excluded because its b=8 would push the result to [2,8,5] ≠ target.

In Python: foundX = foundY = foundZ = False. For a, b, c in triplets: if a <= x and b <= y and c <= z: foundX |= (a == x); foundY |= (b == y); foundZ |= (c == z). Return foundX and foundY and foundZ. This is about 6 lines.

In Java: boolean foundX = false, foundY = false, foundZ = false. For each int[] t in triplets: if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]): update flags. Return foundX && foundY && foundZ.

An alternative approach uses a set of "good indices": for each valid triplet, add which positions match the target to a set. If the set has all three indices {0, 1, 2}, return true. This is equivalent but slightly less direct.

Time complexity is O(n) where n is the number of triplets. One pass through the array with O(1) work per triplet. No sorting, no nested loops, no data structures.

Space complexity is O(1). Only three boolean flags and loop variables. The input is read-only — no modifications or copies needed.

This is optimal. Any algorithm must examine every triplet at least once (a single unexamined triplet could be the only one providing a needed target value). O(n) time and O(1) space is the theoretical minimum.

Jump Game (LeetCode 55) and Jump Game II (LeetCode 45) share the greedy decision-making structure: at each step, determine what is achievable and track whether the goal is reachable. The triplet filter is analogous to checking if a jump overshoots the target.

Gas Station (LeetCode 134) is another single-pass greedy where you track feasibility as you scan. Both problems maintain simple state variables (boolean flags or running sums) that determine the answer at the end.

Hand of Straights (LeetCode 846) and Divide Array in Sets of K Consecutive Numbers (LeetCode 1296) are greedy grouping problems. While the mechanics differ, the shared theme is determining if a target configuration is achievable from given elements.