Count Items Matching a Rule

Description

You are given a collection of triplets, where each triplet is an array of three integers, along with a target triplet. Your goal is to determine whether you can form the target triplet by repeatedly merging pairs of triplets using a special operation.

The merge operation works as follows: pick any two different triplets at indices i and j, then update the triplet at index j so that each of its three values becomes the maximum of the corresponding values from triplets i and j. Formally, triplets[j] becomes [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)].

You may perform this operation any number of times (including zero). Return true if it is possible for the target triplet to appear as an element of the triplets array after some sequence of operations, or false otherwise.

Examples

Example 1

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

Output: true

Explanation: We can merge the first triplet [2,5,3] with the last triplet [1,7,5]. The result is [max(2,1), max(5,7), max(3,5)] = [2,7,5], which matches the target. Note that the middle triplet [1,8,4] was not used because its second value 8 would overshoot the target's second value 7.

Example 2

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

Output: false

Explanation: No combination of merges can produce [3,2,5]. The target requires a value of 2 at position 1, but neither triplet has a 2 at any position. Since the merge operation uses maximum, we can never produce a value that doesn't already exist in at least one triplet at that position.

Example 3

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

Output: true

Explanation: First merge [2,5,3] with [1,2,5] to get [2,5,5]. Then merge [2,5,5] with [5,2,3] to get [5,5,5], which equals the target. All four triplets are safe to use since we can selectively combine values from different triplets to reach [5,5,5].

Constraints

1 ≤ triplets.length ≤ 10^5
triplets[i].length == target.length == 3
1 ≤ a_i, b_i, c_i, x, y, z ≤ 1000

Editorial

Brute Force

Intuition

The most straightforward approach is to try every possible combination of triplets and check if merging them produces the target.

Since the merge operation takes the element-wise maximum, the order in which we merge doesn't matter — only which triplets we include matters. Merging triplets A, B, and C in any order always yields the same result: [max of all first values, max of all second values, max of all third values].

Think of it like mixing paint colors where each mix only keeps the darkest shade at each position. You're trying to find some combination of paints that, when mixed together, gives you exactly the target shade at all three positions.

We can enumerate every possible non-empty subset of triplets (from single triplets to all of them), compute the element-wise maximum for each subset, and check whether any subset's merged result matches the target exactly.

Step-by-Step Explanation

Let's trace through with triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]:

Step 1: Check each single triplet first. Subset = {[2,5,3]}.

Merged result: [2, 5, 3]
Does [2, 5, 3] equal [2, 7, 5]? No — positions 1 and 2 don't match (5 ≠ 7, 3 ≠ 5).

Step 2: Subset = {[1,8,4]}.

Merged result: [1, 8, 4]
Does [1, 8, 4] equal [2, 7, 5]? No — all three positions differ.

Step 3: Subset = {[1,7,5]}.

Merged result: [1, 7, 5]
Does [1, 7, 5] equal [2, 7, 5]? No — position 0 doesn't match (1 ≠ 2).

Step 4: No single triplet works. Try pairs. Subset = {[2,5,3], [1,8,4]}.

Merged: [max(2,1), max(5,8), max(3,4)] = [2, 8, 4]
Does [2, 8, 4] equal [2, 7, 5]? No — position 1 overshoots (8 > 7).

Step 5: Subset = {[2,5,3], [1,7,5]}.

Merged: [max(2,1), max(5,7), max(3,5)] = [2, 7, 5]
Does [2, 7, 5] equal [2, 7, 5]? YES! Found the target!

Step 6: Return true. The subset {[2,5,3], [1,7,5]} merges to form the target exactly.

Brute Force — Checking All Subsets of Triplets — Watch how we systematically try every possible subset of triplets, computing the element-wise maximum for each, until we find one that matches the target.

Algorithm

For every non-empty subset of triplets (using a bitmask from 1 to 2^n - 1):
a. Initialize merged values d = 0, e = 0, f = 0
b. For each triplet in the current subset, update: d = max(d, triplet[0]), e = max(e, triplet[1]), f = max(f, triplet[2])
c. If [d, e, f] equals the target, return true
If no subset matches, return false

Code

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        int n = triplets.size();
        for (int mask = 1; mask < (1 << n); mask++) {
            int d = 0, e = 0, f = 0;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    d = max(d, triplets[i][0]);
                    e = max(e, triplets[i][1]);
                    f = max(f, triplets[i][2]);
                }
            }
            if (d == target[0] && e == target[1] && f == target[2]) {
                return true;
            }
        }
        return false;
    }
};

class Solution:
    def mergeTriplets(self, triplets: list[list[int]], target: list[int]) -> bool:
        n = len(triplets)
        for mask in range(1, 1 << n):
            d, e, f = 0, 0, 0
            for i in range(n):
                if mask & (1 << i):
                    d = max(d, triplets[i][0])
                    e = max(e, triplets[i][1])
                    f = max(f, triplets[i][2])
            if [d, e, f] == target:
                return True
        return False

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        int n = triplets.length;
        for (int mask = 1; mask < (1 << n); mask++) {
            int d = 0, e = 0, f = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    d = Math.max(d, triplets[i][0]);
                    e = Math.max(e, triplets[i][1]);
                    f = Math.max(f, triplets[i][2]);
                }
            }
            if (d == target[0] && e == target[1] && f == target[2]) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(2^n × n)

We iterate through all 2^n - 1 non-empty subsets. For each subset, we scan all n triplets to determine which are included (using the bitmask) and compute the element-wise maximum. This gives O(n) work per subset, totaling O(2^n × n).

Space Complexity: O(1)

We only use three integer variables (d, e, f) plus the loop counters. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force enumerates all 2^n subsets, which is catastrophically slow. With n up to 10^5, computing 2^(100,000) subsets is completely impossible — the universe doesn't have enough time or atoms for this computation.

The fundamental problem is that we're treating every triplet combination as independent, ignoring a powerful property of the merge operation.

Key insight: The merge operation uses max, which means values can only increase or stay the same — they can never decrease. This has a critical consequence: if any triplet has a value that exceeds the corresponding target value at any position, that triplet is "poisonous." Including it in any merge would permanently push that position above the target, with no way to bring it back down.

This means we can immediately discard all poisonous triplets. Among the remaining safe triplets (where every value is ≤ the target), we can merge them all freely without worry — the result will never overshoot. The best we can possibly achieve is the element-wise maximum across all safe triplets. If that maximum equals the target, we win. If not, it's impossible.

This eliminates the need for subset enumeration entirely, reducing the problem to a single pass through the triplets.

Optimal Approach - Greedy Filter

Intuition

Let's think about what the merge operation really does. When you merge two triplets, each position takes the maximum of the two values. This means values can only increase or stay the same — they can never decrease.

This leads to a critical observation: if any triplet has even one value that exceeds the corresponding target value, that triplet is "poisonous." Including it in any merge would push that position above the target, and since values can only go up, we could never bring it back down.

For example, if our target is [2, 7, 5] and we have a triplet [1, 8, 4], the middle value 8 exceeds the target's 7. Any merge involving this triplet would result in a middle value of at least 8, overshooting our target.

So we can safely ignore all poisonous triplets. Among the remaining "safe" triplets (where all three values are ≤ the corresponding target values), we can freely merge them without worry.

Here's the beautiful part: among all safe triplets, the best possible outcome from any sequence of merges is simply the element-wise maximum across all of them. If this maximum matches the target at every position, we can form the target. If any position falls short, it means no safe triplet carries the needed value, and it's impossible.

This transforms the problem from exponential subset search into a simple single-pass scan: filter out unsafe triplets, collect the maximum at each position from the safe ones, and check if it equals the target.

Step-by-Step Explanation

Let's trace with triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]:

Step 1: Initialize running maximum values: max_a = 0, max_b = 0, max_c = 0. These track the best achievable value at each position from safe triplets.

Step 2: Process triplet [2,5,3]. Is it safe?

2 ≤ 2? Yes. 5 ≤ 7? Yes. 3 ≤ 5? Yes.
All values within target bounds → SAFE.
Update: max_a = max(0, 2) = 2, max_b = max(0, 5) = 5, max_c = max(0, 3) = 3.
Running max: [2, 5, 3]

Step 3: Process triplet [1,8,4]. Is it safe?

1 ≤ 2? Yes. 8 ≤ 7? NO!
Position 1 exceeds target → UNSAFE. Skip this triplet entirely.
Running max stays: [2, 5, 3]

Step 4: Process triplet [1,7,5]. Is it safe?

1 ≤ 2? Yes. 7 ≤ 7? Yes. 5 ≤ 5? Yes.
All values within target bounds → SAFE.
Update: max_a = max(2, 1) = 2, max_b = max(5, 7) = 7, max_c = max(3, 5) = 5.
Running max: [2, 7, 5]

Step 5: All triplets processed. Final running max = [2, 7, 5].

Does [2, 7, 5] equal target [2, 7, 5]? YES!

Step 6: Return true. The safe triplets collectively contribute all the values needed to reach the target.

Greedy Filter — Single Pass Through Triplets — Watch how we process each triplet in one pass: check if it's safe (all values ≤ target), and if so, update our running maximum. Unsafe triplets are skipped entirely.

Algorithm

Extract the target values: x, y, z = target
Initialize three running maximum variables: max_a = 0, max_b = 0, max_c = 0
For each triplet [a, b, c] in the input:
- If a ≤ x AND b ≤ y AND c ≤ z (all values within target bounds):
  - Update: max_a = max(max_a, a), max_b = max(max_b, b), max_c = max(max_c, c)
- Otherwise, skip this triplet (it's unsafe)
Return true if [max_a, max_b, max_c] equals [x, y, z], false otherwise

Code

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        int x = target[0], y = target[1], z = target[2];
        int maxA = 0, maxB = 0, maxC = 0;
        
        for (auto& t : triplets) {
            if (t[0] <= x && t[1] <= y && t[2] <= z) {
                maxA = max(maxA, t[0]);
                maxB = max(maxB, t[1]);
                maxC = max(maxC, t[2]);
            }
        }
        
        return maxA == x && maxB == y && maxC == z;
    }
};

class Solution:
    def mergeTriplets(self, triplets: list[list[int]], target: list[int]) -> bool:
        x, y, z = target
        max_a, max_b, max_c = 0, 0, 0
        
        for a, b, c in triplets:
            if a <= x and b <= y and c <= z:
                max_a = max(max_a, a)
                max_b = max(max_b, b)
                max_c = max(max_c, c)
        
        return [max_a, max_b, max_c] == [x, y, z]

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        int x = target[0], y = target[1], z = target[2];
        int maxA = 0, maxB = 0, maxC = 0;
        
        for (int[] t : triplets) {
            if (t[0] <= x && t[1] <= y && t[2] <= z) {
                maxA = Math.max(maxA, t[0]);
                maxB = Math.max(maxB, t[1]);
                maxC = Math.max(maxC, t[2]);
            }
        }
        
        return maxA == x && maxB == y && maxC == z;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array of triplets exactly once. For each triplet, we perform a constant number of comparisons (3 for the safety check) and at most 3 max operations. This gives O(1) work per triplet, and O(n) total for n triplets.

Space Complexity: O(1)

We only use a fixed number of variables: x, y, z for the target values, and max_a, max_b, max_c for the running maximums. These do not grow with input size, so the space usage is constant.

This is a massive improvement over the brute force: from O(2^n × n) time to O(n) time, making it easily handle n = 10^5 within milliseconds.