LeetCode 1899 - Merge Triplets to Form Target Triplet

The problem asks whether it is possible to create a specific target triplet [x, y, z] as an element of a given list of triplets by repeatedly merging pairs of triplets using a component-wise maximum operation.

leetcodemediumarraygreedy

LeetCode Problem 1899

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem asks whether it is possible to create a specific target triplet [x, y, z] as an element of a given list of triplets by repeatedly merging pairs of triplets using a component-wise maximum operation. Each triplet is a list of three integers, representing values along three dimensions. The operation allows us to choose any two triplets i and j and update triplets[j] to [max(ai, aj), max(bi, bj), max(ci, cj)].

The input consists of a 2D integer array triplets with size up to 10^5 and a target triplet of size three. The output is a boolean: true if the target can appear as an element after any number of operations, and false otherwise.

Key points include:

  • Each number in a triplet is between 1 and 1000, so we do not need to worry about negative numbers or zero.
  • The triplets can be updated many times, but updates are only allowed by taking the max component-wise.
  • For a number in target to appear in the final result, there must exist at least one triplet in triplets where the corresponding component is less than or equal to the target component (no triplet can "decrease" a component).

Important edge cases:

  • If any component of target is smaller than all available corresponding components in triplets, the target cannot be obtained.
  • If triplets already contains the target, the function should immediately return true.
  • If all triplets have at least one component exceeding the target in the wrong dimension, merging cannot reduce that value, so the target is impossible.

Approaches

Brute Force

A naive approach would simulate all possible merge operations between pairs of triplets. At each step, we would attempt every combination of two triplets and update one according to the component-wise maximum. We would continue until no further changes occur, then check whether the target exists in triplets.

This approach is correct because it explores all possible outcomes, but it is too slow for large inputs. With up to 10^5 triplets, simulating every pair would require O(n^2) operations per merge step, which is infeasible.

Optimal Insight

The key observation is that we only care about achieving the target component-wise. Any triplet where a component exceeds the corresponding target component is useless for forming the target in that dimension, because max will never decrease values. Thus, we only need to find triplets that are valid candidates (all components ≤ target) and check if, for each dimension, there exists a triplet that matches the target exactly in that dimension when merged.

By keeping track of which components of the target can be "covered" by valid triplets, we can determine if all three components can eventually be formed without simulating all merge operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) per merge step O(n) Simulate every possible merge operation until convergence. Too slow for n = 10^5.
Optimal O(n) O(1) Track components that can reach the target using only valid triplets. Simple linear scan suffices.

Algorithm Walkthrough

  1. Initialize a boolean array found = [False, False, False] to track whether each component of the target can be obtained. found[0] corresponds to target[0], and so on.
  2. Iterate through each triplet in triplets.
  3. For each triplet, check if it is valid. A triplet is valid if all its components are ≤ the corresponding components in target. If any component exceeds the target, ignore this triplet since it cannot help form the target.
  4. For a valid triplet, check each component. If a component matches the target, mark the corresponding found entry as True.
  5. After scanning all triplets, check if all entries in found are True. If they are, return True; otherwise, return False.

Why it works:

Each component of the target can be formed by merging triplets that are valid and have that component equal to the target. Because the merge operation takes the maximum, once we have one triplet with the correct component, we can propagate it via merges to form the full target triplet. Valid triplets never exceed the target in any dimension, so merging them cannot invalidate the target components.

Python Solution

from typing import List

class Solution:
    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
        found = [False, False, False]
        
        for triplet in triplets:
            if all(triplet[i] <= target[i] for i in range(3)):
                for i in range(3):
                    if triplet[i] == target[i]:
                        found[i] = True
                        
        return all(found)

Explanation:

The code initializes a found array to track which target components are achievable. It iterates over each triplet, checking if it is valid. For valid triplets, any component equal to the target is marked True. Finally, if all components are found, the target can be formed.

Go Solution

func mergeTriplets(triplets [][]int, target []int) bool {
    found := [3]bool{}

    for _, triplet := range triplets {
        valid := true
        for i := 0; i < 3; i++ {
            if triplet[i] > target[i] {
                valid = false
                break
            }
        }
        if valid {
            for i := 0; i < 3; i++ {
                if triplet[i] == target[i] {
                    found[i] = true
                }
            }
        }
    }

    return found[0] && found[1] && found[2]
}

Go-specific notes:

We use a fixed-size boolean array instead of a slice for simplicity. The valid flag ensures we skip triplets exceeding the target. The logic mirrors the Python version exactly.

Worked Examples

Example 1: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]

triplet valid? found after update
[2,5,3] True [True, False, False]
[1,8,4] False [True, False, False]
[1,7,5] True [True, True, True]

All found are True, so return True.

Example 2: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]

triplet valid? found after update
[3,4,5] False [False, False, False]
[4,5,6] False [False, False, False]

Not all components found, so return False.

Example 3: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]

triplet valid? found after update
[2,5,3] True [False, True, False]
[2,3,4] True [False, True, False]
[1,2,5] True [False, True, True]
[5,2,3] True [True, True, True]

Return True.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterate once over all n triplets, checking three components each.
Space O(1) Constant extra space for found array and temporary variables.

The linear time complexity is optimal because we must at least look at every triplet once. Space is constant because we do not need extra structures that scale with n.

Test Cases

# Provided examples
assert Solution().mergeTriplets([[2,5,3],[1,8,4],[1,7,5]], [2,7,5]) == True  # Example 1
assert Solution().mergeTriplets([[3,4,5],[4,5,6]], [3,2,5]) == False         # Example 2
assert Solution().mergeTriplets([[2,5,3],[2,3,4],[1,2,5],[5,2,3]], [5,5,5]) == True  # Example 3

# Edge cases
assert Solution().mergeTriplets([[1,1,1]], [1,1,1]) == True  # Single triplet equals target
assert Solution().mergeTriplets([[1,2,3]], [3,2,1]) == False # Single triplet cannot form target
assert Solution().mergeTriplets([[1,2,3],[3,2,