1899. Merge Triplets to Form Target

At a Glance

• Topic: greedy
• Pattern: Greedy (coordinate-wise feasibility filter)
• Difficulty: Medium
• Companies: Google, Amazon, Meta, Citadel
• Frequency: Medium
• LeetCode: 1899

Problem (one-liner)

Given triplets [first, second, third] and a target triplet, you may repeatedly merge any triplet into another by taking coordinate-wise max of chosen pairs. Determine whether target can be formed without ever exceeding target on any coordinate during merges. Input: triplets, target. Output: boolean.

Recognition Cues

• “Merge triplets” via coordinate-wise max
• Discard any triplet that exceeds target on any axis (cannot be used without overshooting)
• After filter, check max per coordinate across remaining covers target

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Search — unnecessary.
• Greedy filter + aggregate max — O(n) time / O(1) space beyond input pointer. <- pick this in interview.

Optimal Solution

Go

package main

func mergeTriplets(triplets [][]int, target []int) bool {
	targetFirst := target[0]
	targetSecond := target[1]
	targetThird := target[2]
	hasExactFirst := false
	hasExactSecond := false
	hasExactThird := false
	for _, triplet := range triplets {
		first := triplet[0]
		second := triplet[1]
		third := triplet[2]
		if first > targetFirst || second > targetSecond || third > targetThird {
			continue
		}
		if first == targetFirst {
			hasExactFirst = true
		}
		if second == targetSecond {
			hasExactSecond = true
		}
		if third == targetThird {
			hasExactThird = true
		}
	}
	return hasExactFirst && hasExactSecond && hasExactThird
}

JavaScript

function mergeTriplets(triplets, target) {
	const [targetFirst, targetSecond, targetThird] = target;
	let hasExactFirst = false;
	let hasExactSecond = false;
	let hasExactThird = false;
	for (const triplet of triplets) {
		const [first, second, third] = triplet;
		if (first > targetFirst || second > targetSecond || third > targetThird) {
			continue;
		}
		if (first === targetFirst) hasExactFirst = true;
		if (second === targetSecond) hasExactSecond = true;
		if (third === targetThird) hasExactThird = true;
	}
	return hasExactFirst && hasExactSecond && hasExactThird;
}

Walkthrough

Skip unsafe triplets (any coordinate strictly greater than target). Among safe triplets, each coordinate of target must appear exactly on at least one triplet at that position—those coordinates can be inherited through merges without exceeding target.

Edge Cases

• Target zero components — triplet [0,0,0] may be required
• Duplicate triplets — harmless

Pitfalls

• Marking only “all coordinates ≤ target” and then taking coordinate-wise max—not sufficient; you must record which target coordinates are hit exactly by at least one safe triplet.
• Skipping the filter on invalid triplets (any axis above target) first.

Similar Problems

• 056. Merge Intervals — merge pattern vocabulary.
• 435. Non-overlapping Intervals — greedy filtering.
• 763. Partition Labels — greedy feasibility using constraints.

Variants

• Cost per merge → optimization, not this decision problem.

Mind-Map Tags

#greedy #coordinate-max #filter #medium