Difficulty: Medium · LeetCode 1899

Problem

Given a list of triplets and a target triplet, you can merge any two triplets by taking the element-wise max. Return True if you can form the target.

Understanding the problem

Merging uses max(), so any triplet where one coordinate exceeds the target can never be used — it would permanently overshoot that coordinate. Filter those out and check if the remaining triplets collectively cover every coordinate of the target.

Intuition

Discard every triplet where any coordinate exceeds the target (merging would lock us above target). Among the remaining valid triplets, check whether we can find the exact target values at each coordinate position.

Approach

Initialize found = [False, False, False].
For each triplet: if any triplet[i] > target[i], skip it entirely.
Otherwise, for each position i: if triplet[i] == target[i], set found[i] = True.
Return all(found).

Naive Solution — Brute Force

DFS trying all subsets: include or exclude each triplet, merge, and check against target.

Python

class Solution:
    def mergeTriplets(self, triplets, target):
        n = len(triplets)

        def dfs(index, current):
            if current == target:
                return True

            if index == n:
                return False

            if dfs(index + 1, current):
                return True

            triplet = triplets[index]

            if all(
                triplet[i] <= target[i]
                for i in range(3)
            ):
                merged = [
                    max(current[i], triplet[i])
                    for i in range(3)
                ]

                if dfs(index + 1, merged):
                    return True

            return False

        return dfs(0, [0, 0, 0])

C++

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        return dfs(triplets, target, 0, {0, 0, 0});
    }

private:
    bool dfs(vector<vector<int>>& triplets, vector<int>& target, int index, vector<int> current) {
        if (current == target) {
            return true;
        }

        if (index == (int)triplets.size()) {
            return false;
        }

        if (dfs(triplets, target, index + 1, current)) {
            return true;
        }

        vector<int>& triplet = triplets[index];

        if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
            vector<int> merged(3);
            for (int i = 0; i < 3; i++) {
                merged[i] = max(current[i], triplet[i]);
            }

            if (dfs(triplets, target, index + 1, merged)) {
                return true;
            }
        }

        return false;
    }
};

Java

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        return dfs(triplets, target, 0, new int[]{0, 0, 0});
    }

    private boolean dfs(int[][] triplets, int[] target, int index, int[] current) {
        if (Arrays.equals(current, target)) {
            return true;
        }

        if (index == triplets.length) {
            return false;
        }

        if (dfs(triplets, target, index + 1, current)) {
            return true;
        }

        int[] triplet = triplets[index];

        if (triplet[0] <= target[0] && triplet[1] <= target[1] && triplet[2] <= target[2]) {
            int[] merged = new int[3];
            for (int i = 0; i < 3; i++) {
                merged[i] = Math.max(current[i], triplet[i]);
            }

            if (dfs(triplets, target, index + 1, merged)) {
                return true;
            }
        }

        return false;
    }
}

JavaScript

var mergeTriplets = function(triplets, target) {
    const n = triplets.length;

    const dfs = (index, current) => {
        if (current.every((v, i) => v === target[i])) {
            return true;
        }

        if (index === n) {
            return false;
        }

        if (dfs(index + 1, current)) {
            return true;
        }

        const triplet = triplets[index];

        if (triplet.every((v, i) => v <= target[i])) {
            const merged = current.map((v, i) => Math.max(v, triplet[i]));

            if (dfs(index + 1, merged)) {
                return true;
            }
        }

        return false;
    };

    return dfs(0, [0, 0, 0]);
};

Time: O(2ⁿ) · Space: O(n) recursion

Optimized Code (Python 3)

Python

class Solution:
    def mergeTriplets(self, triplets, target):
        found = [False, False, False]

        for triplet in triplets:
            if any(
                triplet[i] > target[i]
                for i in range(3)
            ):
                continue

            for i in range(3):
                if triplet[i] == target[i]:
                    found[i] = True

        return all(found)

C++

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        bool found[3] = {false, false, false};

        for (auto& triplet : triplets) {
            if (triplet[0] > target[0] || triplet[1] > target[1] || triplet[2] > target[2]) {
                continue;
            }

            for (int i = 0; i < 3; i++) {
                if (triplet[i] == target[i]) {
                    found[i] = true;
                }
            }
        }

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

Java

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        boolean[] found = new boolean[3];

        for (int[] triplet : triplets) {
            if (triplet[0] > target[0] || triplet[1] > target[1] || triplet[2] > target[2]) {
                continue;
            }

            for (int i = 0; i < 3; i++) {
                if (triplet[i] == target[i]) {
                    found[i] = true;
                }
            }
        }

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

JavaScript

var mergeTriplets = function(triplets, target) {
    const found = [false, false, false];

    for (const triplet of triplets) {
        if (triplet.some((v, i) => v > target[i])) {
            continue;
        }

        for (let i = 0; i < 3; i++) {
            if (triplet[i] === target[i]) {
                found[i] = true;
            }
        }
    }

    return found.every(Boolean);
};

Time: O(n) · Space: O(1)

Takeaway

Pattern — Greedy Filtering — eliminate impossible candidates (those that overshoot), then verify coverage