Leetcode 1899: Merge Triplets to Form Target Triplet

Input: You are given a 2D array `triplets`, where each element is a triplet of integers, and a target triplet `target`. You can update the triplets using a series of operations as described.

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

Constraints:

• 1 <= triplets.length <= 10^5

• triplets[i].length == target.length == 3

• 1 <= ai, bi, ci, x, y, z <= 1000

Output: Return `true` if it's possible to form the target triplet from the given triplets through the allowed operations, otherwise return `false`.

Example: true

Constraints:

• The output must be a boolean value indicating if the target triplet can be formed.

Goal: The goal is to determine if we can obtain the target triplet through the allowed operations.

Steps:

• Iterate over each triplet and check if each element can potentially form the target triplet by updating other triplets.

• For each triplet, keep track of the maximum values seen so far and compare them to the target.

Goal: Ensure that the input respects the given constraints.

Steps:

• 1 <= triplets.length <= 10^5

• 1 <= ai, bi, ci, x, y, z <= 1000

Assumptions:

• All triplets and the target triplet are non-negative integers.

• Triplets are updated through the specified operation and no other operations are allowed.

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

• Explanation: Through the operation on triplets, the target triplet can be formed by updating the last triplet to match the target.

Approach: The problem can be solved by iterating over the triplets, updating the maximum values, and checking if the target triplet can be formed.

Observations:

• The operation involves taking maximum values between corresponding elements of two triplets.

• We need to check if it's possible to form the target by applying this operation.

• We can track the maximum values as we process each triplet and compare them to the target.

Steps:

• Iterate over the `triplets` and apply the maximum operation on the relevant triplets.

• Compare the resulting values to the target triplet.

• Return true if the target is formed, otherwise return false.

Empty Inputs:

• Empty lists are not allowed in the input.

Large Inputs:

• The solution should handle up to 10^5 triplets efficiently.

Special Values:

• The triplets and target values are always positive integers.

Constraints:

• Ensure that the input meets the constraints, especially for large inputs.


bool mergeTriplets(vector<vector<int>>& tri, vector<int>& tgt) {
    vector<int> res(3, 0);
    int n = tri.size();

    for(auto s: tri) {
        if(s[0] <= tgt[0] && s[1] <= tgt[1] && s[2] <= tgt[2]) {
            res = { max(res[0], s[0]), max(res[1], s[1]), max(res[2], s[2]) };
        }
    }
    
    return tgt == res;        
}

1 : Function Definition

bool mergeTriplets(vector<vector<int>>& tri, vector<int>& tgt) {

Define the function `mergeTriplets`, which takes a vector of triplets `tri` and a target triplet `tgt`.

2 : Initialize Result Triplet

    vector<int> res(3, 0);

Initialize the result triplet `res` with 3 zeros. This will store the maximum values from the triplets in `tri` that can contribute to the target `tgt`.

3 : Get Triplet Count

    int n = tri.size();

Get the number of triplets in `tri` and store it in `n`. This value is not used explicitly later in the function but helps describe the size of `tri`.

4 : Loop Through Triplets

    for(auto s: tri) {

Start a loop to iterate through each triplet `s` in `tri`.

5 : Condition Check

        if(s[0] <= tgt[0] && s[1] <= tgt[1] && s[2] <= tgt[2]) {

Check if all elements of the current triplet `s` are less than or equal to the corresponding elements in the target triplet `tgt`.

6 : Update Result Triplet

            res = { max(res[0], s[0]), max(res[1], s[1]), max(res[2], s[2]) };

Update the result triplet `res` with the maximum values from the current triplet `s` and the previously stored values in `res`.

7 : Return Statement

    return tgt == res;

Return `true` if the resulting triplet `res` matches the target `tgt`, otherwise return `false`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The solution iterates through the list of triplets once, so the time complexity is linear in the size of the input.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant, as we only store the maximum values for each element in the triplets.

Leetcode 1899: Merge Triplets to Form Target Triplet

Explore →