Merge Triplets to Form Target Triplet

LeetCode 1899: Merge Triplets to Form Target Triplet Solution & Explanation

Problem Overview

TL;DR: Ignore every triplet that exceeds the target in any coordinate, then greedily record whether the remaining triplets can provide each target coordinate exactly.

In LeetCode 1899: Merge Triplets to Form Target Triplet, each selected triplet contributes three coordinates. Merging selected triplets takes the maximum value independently at each position. The goal is to determine whether some selection can produce the target triplet exactly.

A valid solution must satisfy two conditions:

1. No selected triplet can exceed the target in any coordinate.
2. Across the valid triplets, every target coordinate must be matched by at least one triplet.

This Merge Triplets to Form Target Triplet problem is a popular interview question because it tests greedy filtering, coordinate-wise constraints, and invariant maintenance. The resulting one-pass method is an optimal solution for interviews.

Brute Force Approach for Merge Triplets to Form Target Triplet

A direct approach is to consider every possible subset of triplets:

1. Select a subset of the input triplets.
2. Merge the selected triplets by taking the maximum at each of the three coordinates.
3. Compare the resulting triplet with target.
4. Return true if any subset produces the target.

Naive Pseudocode

for every subset of triplets:
    merged = [negative_infinity, negative_infinity, negative_infinity]

    for triplet in subset:
        for coordinate from 0 to 2:
            merged[coordinate] =
                max(merged[coordinate], triplet[coordinate])

    if merged == target:
        return true

return false

With n triplets, there are 2^n possible subsets. Merging one subset can require up to O(n) work, so the total complexity is:

O(n * 2^n)

The constraints allow up to 10^5 triplets. Exponential time is infeasible at that size and would result in Time Limit Exceeded, even before accounting for the work required to merge each subset.

Algorithm Strategy: Greedy Patterns

Maintain a Boolean array of length three to record which target coordinates have been matched.

For every triplet:

1. Check whether any coordinate is greater than the corresponding target coordinate.
2. If so, reject the triplet because it cannot participate in a valid merge.
3. Otherwise, inspect all three coordinates.
4. Mark a coordinate as matched when it equals the corresponding target value.

After processing all triplets, return true only if all three coordinates are marked.

No sorting is needed because the decision for each triplet depends only on its relationship with the fixed target. The state records all information relevant to future triplets.

Execution Flow

1. Initialize:

   textCopy

   matched = [false, false, false]

2. Read the next triplet.

3. Compare its three coordinates with the target:

   • If triplet[0] > target[0], reject it.
   • If triplet[1] > target[1], reject it.
   • If triplet[2] > target[2], reject it.

4. For a non-rejected triplet:

   • If its first coordinate equals target[0], set matched[0] = true.
   • If its second coordinate equals target[1], set matched[1] = true.
   • If its third coordinate equals target[2], set matched[2] = true.

5. Continue until every triplet has been processed.

6. Return:

   textCopy

   matched[0] && matched[1] && matched[2]

For example, with target = [2, 4, 5]:

• [2, 4, 1] is valid and matches the first two coordinates.
• [1, 3, 5] is valid and matches the third coordinate.
• All entries become true, so the target can be formed.

Proof of Correctness

We prove that the algorithm returns true if and only if some collection of triplets can be merged into target.

If the Algorithm Returns true

The algorithm returns true only when every coordinate is marked as matched.

For each coordinate i, there exists a processed triplet t such that:

t[i] == target[i]

That triplet was accepted, so it also satisfies:

t[j] <= target[j] for every coordinate j

Select the triplets responsible for matching the three coordinates. Every selected triplet is coordinate-wise no greater than target, so their merged maximum cannot exceed target. Each coordinate is supplied exactly at the target value by at least one selected triplet, so the merged result cannot be less than target.

Therefore, the merged result is exactly target.

If a Valid Collection Exists

Assume some collection merges to target.

No triplet in that collection can exceed target in any coordinate. If one did, the coordinate-wise maximum would also exceed target, contradicting that the merge equals the target.

For each coordinate i, the merged value equals target[i]. Since all selected values are at most target[i], at least one selected triplet must have value exactly target[i] at coordinate i.

The algorithm does not reject any triplet that could belong to a valid collection. It therefore encounters a valid triplet matching each target coordinate and marks all three entries in matched.

Thus, the algorithm returns true.

Since both directions hold, the algorithm is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 406: Queue Reconstruction by Height
• LeetCode 1029: Two City Scheduling
• LeetCode 455: Assign Cookies
• LeetCode 135: Candy

These problems use greedy decisions to enforce constraints while progressively maintaining a valid state. Queue Reconstruction by Height uses ordered placement, Two City Scheduling compares assignment costs, Assign Cookies matches resources to requirements, and Candy maintains locally necessary allocations. Although the exact operations differ, each problem relies on making safe decisions under fixed constraints rather than enumerating all possibilities.

Reference Implementation

C++ Solution for LeetCode 1899

1class Solution {
2public:
3    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
4        vector<bool> matched(3, false);
5
6        for (const auto& triplet : triplets) {
7            if (triplet[0] > target[0] ||
8                triplet[1] > target[1] ||
9                triplet[2] > target[2]) {
10                continue;
11            }
12
13            for (int i = 0; i < 3; ++i) {
14                if (triplet[i] == target[i]) {
15                    matched[i] = true;
16                }
17            }
18        }
19
20        return matched[0] && matched[1] && matched[2];
21    }
22};

The C++ implementation first filters out every triplet that exceeds the target. For each remaining triplet, it records coordinate matches in matched. Since each entry only changes from false to true, the state directly represents the greedy invariant.

Java Solution for LeetCode 1899

1class Solution {
2    public boolean mergeTriplets(int[][] triplets, int[] target) {
3        boolean[] matched = new boolean[] {false, false, false};
4
5        for (int[] triplet : triplets) {
6            boolean exceeds = false;
7            for (int i = 0; i < 3; i++) {
8                if (triplet[i] > target[i]) {
9                    exceeds = true;
10                    break;
11                }
12            }
13
14            if (exceeds) {
15                continue;
16            }
17
18            for (int i = 0; i < 3; i++) {
19                if (triplet[i] == target[i]) {
20                    matched[i] = true;
21                }
22            }
23        }
24
25        return matched[0] && matched[1] && matched[2];
26    }
27}

The Java version uses one loop to detect whether a triplet exceeds the target and a second loop to record exact matches only for accepted triplets. The Boolean array remains constant in size.

Python Solution for LeetCode 1899

1from typing import List, Optional
2
3
4class Solution:
5    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
6        matched = [False, False, False]
7
8        for triplet in triplets:
9            if any(triplet[i] > target[i] for i in range(3)):
10                continue
11
12            for i in range(3):
13                if triplet[i] == target[i]:
14                    matched[i] = True
15
16        return all(matched)

The Python implementation applies the same greedy filtering rule with any(...). It then updates the three Boolean positions for every triplet that remains coordinate-wise within the target.