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

Minimum Operations to Make a Subsequence

Number: 1832

Difficulty: Hard

Paid? No

Companies: Amazon, Microsoft, Google

Problem Description

Given two arrays target and arr, the goal is to determine the minimum number of insert operations needed on arr so that target becomes a subsequence of arr. The target array contains distinct integers, while arr may include duplicates. An insert operation allows you to add any integer at any position in arr.

Key Insights

  • Map each value in target to its index so that the relative order in target is maintained.
  • Transform arr into a sequence of indices based on the mapping (ignoring elements not in target).
  • The problem then reduces to finding the Longest Increasing Subsequence (LIS) in this transformed sequence.
  • The minimum operations required equals the length of target minus the length of the LIS.

Space and Time Complexity

Time Complexity: O(n log n) where n is the length of arr (each element is processed and binary search is used for the LIS). Space Complexity: O(n) for storing the mapped sequence and the auxiliary list used in computing the LIS.

Solution

We start by creating a mapping from each element in target to its index. Then, iterate through arr and, for each element that exists in target, convert it to its corresponding index. This gives us a new sequence. The task of finding the longest matching subsequence in arr now becomes finding the longest increasing subsequence (LIS) in this new sequence, which can be efficiently computed using a binary search technique. The final answer is obtained by subtracting the length of this LIS from the length of target.

Code Solutions

def minOperations(target, arr):
    # Create a dictionary to map target values to their indices.
    index_map = {value: idx for idx, value in enumerate(target)}
    
    # Build the sequence of target indices from arr.
    sequence = []
    for num in arr:
        if num in index_map:
            sequence.append(index_map[num])
    
    # Helper function to compute length of longest increasing subsequence (LIS) using binary search.
    def length_of_LIS(seq):
        import bisect
        lis = []
        for x in seq:
            pos = bisect.bisect_left(lis, x)
            if pos == len(lis):
                lis.append(x)
            else:
                lis[pos] = x
        return len(lis)
    
    lis_length = length_of_LIS(sequence)
    # The minimum operations is the difference between the length of target and the length of LIS.
    return len(target) - lis_length

# Example usage:
print(minOperations([5,1,3], [9,4,2,3,4]))  # Expected output: 2
← Back to All Questions