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.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

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

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

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