We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Merge Triplets to Form Target Triplet

Number: 2026

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a list of triplets (arrays of three integers) and a target triplet, determine if it is possible to obtain the target by repeatedly merging two triplets. Merging is done by choosing two distinct triplets and updating one of them to be the element-wise maximum. The goal is to see if, after some sequence of these merge operations, the target triplet appears among the list.

Key Insights

  • Only consider triplets that are "valid" in the sense that none of its values exceed the corresponding target value.
  • For each component of the target, there must be at least one valid triplet that provides that maximum value.
  • By taking the element-wise maximum across all valid triplets, if we can recreate the target, then the target can be formed using a series of allowed operations.

Space and Time Complexity

Time Complexity: O(n), where n is the number of triplets. Space Complexity: O(1) extra space.

Solution

The solution approach involves iterating over the list of triplets and only considering those triplets that do not exceed the target values in any position. For each valid triplet, update a candidate triplet by taking the element-wise maximum with the current candidate. Finally, check if the candidate exactly matches the target triplet. The algorithm uses simple array operations and avoids any extra space beyond a few variables.

Code Solutions

def mergeTriplets(triplets, target):
    # Initialize candidate triplet with zeros
    candidate = [0, 0, 0]
    # Iterate over every triplet in the input list
    for trip in triplets:
        # Only consider triplets where each element is <= corresponding target element
        if trip[0] <= target[0] and trip[1] <= target[1] and trip[2] <= target[2]:
            # Update candidate by taking the element-wise maximum
            candidate[0] = max(candidate[0], trip[0])
            candidate[1] = max(candidate[1], trip[1])
            candidate[2] = max(candidate[2], trip[2])
    # If the candidate matches target, return True; otherwise, return False
    return candidate == target

# Example usage:
triplets = [[2,5,3],[1,8,4],[1,7,5]]
target = [2,7,5]
print(mergeTriplets(triplets, target))  # Output: True
← Back to All Questions