LeetCode · #1899

Merge Triplets to Form Target Solution

Given a list of triplets and a target triplet, determine if you can merge (max per position) a subset to form the target.

01
Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #1899

🏗️

Pattern

Greedy — filter + merge

Given 2D array triplets (each [a,b,c]) and target = [x,y,z], you can merge any subset by taking the max of each position. Return true if some subset merges to exactly target.

Example
Input: triplets = [[2,5,3],[1,8,4],[1,7,5],[2,5,6]] target = [2,7,5] Output: true // Merge triplets[0]=[2,5,3] and triplets[2]=[1,7,5] → max = [2,7,5] ✓
Constraints
• 1 ≤ triplets.length ≤ 10⁵ • triplets[i].length == 3 • 1 ≤ aᵢ, bᵢ, cᵢ, x, y, z ≤ 1000
02
Section Two · Approach 1

Brute Force — O(2ⁿ or n²)

Try all subsets, merge, check if result equals target. Or: try all pairs, check if any pair/single yields target.

Problem: Subset enumeration is 2ⁿ. The greedy insight: a triplet is usable only if none of its values exceeds the corresponding target value. Among usable triplets, check if all three target values are covered.
Java — Check all pairs
class Solution { public boolean mergeTriplets(int[][] t, int[] target) { for (int[] a : t) for (int[] b : t) if (Math.max(a[0],b[0])==target[0] && Math.max(a[1],b[1])==target[1] && Math.max(a[2],b[2])==target[2]) return true; return false; } }
Python — Check all pairs
class Solution: def mergeTriplets(self, triplets: list[list[int]], target: list[int]) -> bool: for a in triplets: for b in triplets: if all(max(a[i],b[i]) == target[i] for i in range(3)): return True return False
MetricValue
TimeO(n²)
SpaceO(1)
03
Section Three · Approach 2

Greedy Filter — O(n) time, O(1) space

A triplet [a,b,c] is safe if a ≤ x, b ≤ y, c ≤ z. Unsafe triplets would push the max above target. Among safe triplets, check if positions 0, 1, and 2 of target are all achievable.

💡 Mental model: Imagine you're mixing paint colors. Target is a specific shade. Each triplet is a paint tube with three color components. Using a tube is "max blending" — each component takes the higher value. A tube that has ANY component higher than target would over-saturate that channel — discard it. Among remaining tubes, check if you can reach the target value for each channel. You just need some safe tube that matches each target channel.
Algorithm
  • Track three booleans (or a set of covered positions).
  • For each triplet: if a ≤ x AND b ≤ y AND c ≤ z (safe):
  • If a == x, mark position 0 covered.
  • If b == y, mark position 1 covered.
  • If c == z, mark position 2 covered.
  • Return true if all three positions are covered.
🎯 When to recognize this pattern: "Can you merge a subset using max/min to form a target?" The insight: filter out elements that would overshoot, then check coverage. O(n) single-pass greedy. The "filter then check" pattern also appears in interval scheduling and subset selection problems.
Why filtering works: Since merge = max, any unsafe triplet (with a value exceeding one target dimension) can never be part of the solution — it would permanently push that dimension above target. Among safe triplets, merging can only increase values (toward target), never exceed it. So we just need coverage.
04
Section Four · Trace

Visual Walkthrough

Trace for triplets=[[2,5,3],[1,8,4],[1,7,5],[2,5,6]], target=[2,7,5].

Merge Triplets — Greedy Filter
Filter: keep triplets with all values ≤ target. Check if each target value is achievable. [2,5,3]: 2≤2,5≤7,3≤5 ✓ safe. a==2→pos0 covered. [1,8,4]: 8>7 ✗ unsafe — discard. [1,7,5]: 1≤2,7≤7,5≤5 ✓ safe. b==7→pos1 covered. c==5→pos2 covered. [2,5,6]: 6>5 ✗ unsafe — discard. All 3 positions covered → return true ✓
05
Section Five · Implementation

Code — Java & Python

Java — Greedy filter
class Solution { public boolean mergeTriplets(int[][] triplets, int[] t) { boolean a = false, b = false, c = false; for (int[] tr : triplets) { if (tr[0] > t[0] || tr[1] > t[1] || tr[2] > t[2]) continue; if (tr[0] == t[0]) a = true; if (tr[1] == t[1]) b = true; if (tr[2] == t[2]) c = true; } return a && b && c; } }
Python — Greedy filter
class Solution: def mergeTriplets(self, triplets: list[list[int]], t: list[int]) -> bool: good = set() for a, b, c in triplets: if a > t[0] or b > t[1] or c > t[2]: continue if a == t[0]: good.add(0) if b == t[1]: good.add(1) if c == t[2]: good.add(2) return len(good) == 3
06
Section Six · Analysis

Complexity Analysis

ApproachTimeSpaceTrade-off
Brute force (all pairs)O(n²)O(1)Only checks pairs, not all subsets
Greedy filter ← optimalO(n)O(1)Single pass; three booleans
07
Section Seven · Edge Cases

Edge Cases & Pitfalls

CaseInputWhy It Matters
Target is a triplet[[2,7,5]], t=[2,7,5]Exact match. All positions covered by one triplet.
All unsafe[[3,3,3]], t=[2,2,2]3>2 in all dimensions. No safe triplets. False.
Partial coverage[[2,1,1],[1,7,1]], t=[2,7,5]Covers positions 0,1 but not 2 (no safe triplet has c=5). False.
Need multiple triplets[[2,1,1],[1,7,1],[1,1,5]], t=[2,7,5]Three safe triplets each cover one position. True.
Single triplet[[1,2,3]], t=[1,2,3]Exact match. True.
⚠ Common Mistake: Not filtering out unsafe triplets. If you include a triplet with a > x, the merge (max) would push dimension 0 above x, and there's no way to bring it back down. A triplet is usable only if all three dimensions are ≤ target. This is the critical insight that makes the O(n) solution work.

← Back to Greedy problems