1899. Merge Triplets to Form Target Triplet

MediumGreedyArray
Leetcode Link

Problem Description

In this problem, your goal is to determine if it is possible to achieve a specific target triplet by applying an operation on a given list of triplets. Each triplet consists of three integers. The operation you can perform involves selecting any two triplets and updating one of them by taking the maximum value for each position to form a new triplet.

Given:

  • A 2D integer array triplets, where triplets[i] = [a_i, b_i, c_i] corresponds to the i-th triplet.
  • An integer array target = [x, y, z], which is the triplet you are trying to create by using the operation on triplets.

The operation you can use is as follows: Choose two different triplets i and j (0-indexed) and update triplet j to be [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)].

The question asks you to return true if it is possible to have the target triplet [x, y, z] as an element of the triplets array after applying the operation any number of times (including zero times), or false otherwise.

Intuition

To solve this problem, the key idea is to realize that each value in the target triplet [x, y, z] must be obtainable by using the max operation within the constraints of the given triplets. To figure this out, we can initialize three variables, d, e, and f, to represent the best candidates for each position of the triplet that we can achieve through the operation.

For each triplet [a, b, c] in triplets, we check if it is "valid" to use this triplet in the operation towards reaching the target. A valid triplet is one where a is less than or equal to x, b is less than or equal to y, and c is less than or equal to z, meaning that this triplet could potentially be used to reach the target without exceeding it.

If a triplet is valid, we update our best candidates (d, e, f) to be the maximum values seen so far that do not exceed the corresponding target values. At the end of this process, if our best candidate triplet [d, e, f] is equal to the target triplet, then we know it is possible to achieve the target triplet; otherwise, it is not possible.

The key insight is that we don't need to consider the actual sequence of operations. We only need to find the highest values (up to the target values) obtainable for each element of the triplet. If any required value cannot be met or exceeded, the target cannot be reached.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What data structure does Breadth-first search typically uses to store intermediate states?

Solution Approach

The solution utilizes a simple but effective approach leveraging the idea of maintainability and upgradability in the context of triplets with respect to our target. We iterate through all the given triplets, updating our candidate triplet [d, e, f] to the best version that could possibly match our target.

Here's the step-by-step breakdown of the solution:

  1. Initialize three integers d, e, f to represent the maximum values we can achieve for each element in the target triplet [x, y, z] without ever exceeding those values.

  2. Iterate through each triplet [a, b, c] in given triplets array.

  3. For each triplet, check whether it's safe to consider it in the progression towards the target:

    a. To be considerate safe, a must be less than or equal to x, b must be less than or equal to y, and c must be less than or equal to z.

    b. If the triplet doesn't conform to these conditions, we discard it as it would take us away from our target by exceeding the intended value in at least one position.

  4. If the triplet [a, b, c] is valid, we take the maximum values between our current candidates [d, e, f] and [a, b, c]. This basically simulates the allowed operation but only in the direction of increasing our chances of reaching the target without going past it:

    a. Update d with max(d, a)

    b. Update e with max(e, b)

    c. Update f with max(f, c)

  5. After iterating through all triplets, check if the candidate triplet [d, e, f] matches the target:

    a. If they match, it implies that we can indeed form the target by potentially merging the triplets without ever needing to exceed the target values.

    b. If they don't match, we conclude that it is not possible to reach the target given the operations and constraints defined.

In this solution, we essentially simulate the process of using the maximum operation to gradually upgrade a fictional triplet starting from [0, 0, 0] to the maximum values that it can reach without exceeding the target values [x, y, z]. If at the end of this process, we have successfully reached [x, y, z], it means that the operations can indeed reconstruct the target triplet from the given array of triplets.

No additional data structures or patterns are required for this approach, as we simply use loop iteration and conditionals to handle the core logic, and rely on basic variable assignments for state tracking.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Consider an example where the triplets array is [[3,4,5], [1,2,3], [2,3,4]] and the target triplet is [2,3,5]. Let's use the solution approach to check if we can achieve the target.

  1. We initialize d, e, f to 0 since we start out with a fictional triplet [0, 0, 0].

  2. Start iterating through the triplets array:

    • First triplet: [3,4,5]
      • Since 3 is greater than 2 (our x value in target), this triplet cannot contribute to forming the first element of the target. We do not update our d, e, f values.
    • Second triplet: [1,2,3]
      • All elements are less than or equal to the corresponding target elements. We can consider this entire triplet.
      • d = max(d, 1) → d = 1
      • e = max(e, 2) → e = 2
      • f = max(f, 3) → f = 3
    • Third triplet: [2,3,4]
      • All elements are less than or equal to the corresponding target elements. We can consider this entire triplet as well.
      • d = max(d, 2) → d = 2
      • e = max(e, 3) → e = 3
      • f = max(f, 4) → f = 4 (Note that f is not equal to 5, which is the target's third value)

  3. After iterating through all triplets, our constructed candidate triplet [d, e, f] is [2,3,4].

  4. Finally, we compare our candidate [2,3,4] with the target [2,3,5]. Since the third element does not match (4 instead of 5), we determine that it is not possible to achieve the target triplet [2,3,5].

In this example walk through, we clearly see how the solution methodically processes each triplet in relation to the target and upgrades the candidate triplet [d, e, f] only in ways that are safe and in accordance with our goal of reaching the target. Despite the operations we carried out, the target's third value was not met, leading us to the conclusion that under the given constraints, forming the target is not possible.

Solution Implementation

1from typing import List
2
3class Solution:
4    def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
5        # Initialize variables to track the maximum values for each position
6        max_x, max_y, max_z = 0, 0, 0
7      
8        # Unpack target values into separate variables for clarity
9        target_x, target_y, target_z = target
10      
11        # Iterate through each triplet in the list of triplets
12        for triplet in triplets:
13            # Unpack the values in the current triplet
14            a, b, c = triplet
15          
16            # Check if the current triplet is valid by comparing it to the target
17            if a <= target_x and b <= target_y and c <= target_z:
18                # Update the maximum values seen so far for each position, if applicable
19                max_x = max(max_x, a)
20                max_y = max(max_y, b)
21                max_z = max(max_z, c)
22      
23        # Return True if the maximum values match the target values, otherwise return False
24        return [max_x, max_y, max_z] == target
25
1class Solution {
2    public boolean mergeTriplets(int[][] triplets, int[] target) {
3        // Extract the target values for easy reference
4        int targetX = target[0];
5        int targetY = target[1];
6        int targetZ = target[2];
7
8        // Initialize the max values found in the triplets
9        int maxX = 0; 
10        int maxY = 0; 
11        int maxZ = 0;
12
13        // Iterate over each triplet in the given array of triplets
14        for (int[] triplet : triplets) {
15            // Extract the values of the current triplet
16            int currentX = triplet[0];
17            int currentY = triplet[1];
18            int currentZ = triplet[2];
19
20            // Check if the current triplet can potentially contribute to
21            // forming the target triplet without exceeding any target value
22            if (currentX <= targetX && currentY <= targetY && currentZ <= targetZ) {
23                // Update the maximum values found that do not exceed the target values
24                maxX = Math.max(maxX, currentX);
25                maxY = Math.max(maxY, currentY);
26                maxZ = Math.max(maxZ, currentZ);
27            }
28        }
29
30        // Return true if the maximum values found match the target values
31        return maxX == targetX && maxY == targetY && maxZ == targetZ;
32    }
33}
34
1class Solution {
2public:
3    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
4        // Extract the target values for comparison.
5        int targetX = target[0], targetY = target[1], targetZ = target[2];
6      
7        // Initialize variables to keep track of the maximum values of the triplets.
8        int maxX = 0, maxY = 0, maxZ = 0;
9      
10        // Iterate over each triplet in the input list.
11        for (auto& triplet : triplets) {
12            // Extract the triplet values for comparison.
13            int currentX = triplet[0], currentY = triplet[1], currentZ = triplet[2];
14          
15            // Check if the current triplet's values are less than or equal
16            // to the corresponding target values.
17            if (currentX <= targetX && currentY <= targetY && currentZ <= targetZ) {
18                // Update the running maxima if the current values are greater.
19                maxX = max(maxX, currentX);
20                maxY = max(maxY, currentY);
21                maxZ = max(maxZ, currentZ);
22            }
23        }
24      
25        // Determine if the largest triplets found match the target triplet.
26        return maxX == targetX && maxY == targetY && maxZ == targetZ;
27    }
28};
29
1/**
2 * Checks whether it is possible to form a target triplet from a set of given triplets.
3 * 
4 * @param {number[][]} triplets - An array containing triplets (arrays of three numbers).
5 * @param {number[]} target - An array of three integers representing the target triplet.
6 * @returns {boolean} - True if the target triplet can be formed, otherwise false.
7 */
8function mergeTriplets(triplets: number[][], target: number[]): boolean {
9    // Destructure the target triplet into the required values.
10    const [targetX, targetY, targetZ] = target;
11
12    // Initialize max values for x, y, z to 0.
13    let [maxX, maxY, maxZ] = [0, 0, 0];
14
15    // Iterate over each triplet in the given array.
16    for (const [tripletX, tripletY, tripletZ] of triplets) {
17        // Check if the values of the current triplet are less than or equal to the target values.
18        if (tripletX <= targetX && tripletY <= targetY && tripletZ <= targetZ) {
19            // Update max values, if the current value is higher than what was seen before.
20            maxX = Math.max(maxX, tripletX);
21            maxY = Math.max(maxY, tripletY);
22            maxZ = Math.max(maxZ, tripletZ);
23        }
24    }
25
26    // Return true if the max values for x, y, z match the target triplet exactly.
27    return maxX === targetX && maxY === targetY && maxZ === targetZ;
28}
29
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of triplets. This is because there is a single loop that iterates over each element in the triplets list once, and within this loop, the operations performed are all constant time operations (comparisons, assignments, and max() function on integers).

The space complexity of the code is O(1), independent of the number of triplets. The only extra space used is for the variables d, e, and f, which hold the maximum values of the first, second, and third elements of the triplets that can be part of the merge to reach the target. The variables x, y, and z are just references to the elements of the target list and do not count towards additional space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫