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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Make a Subsequence

Difficulty: Hard

Problem Description

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates. In one operation, you can insert any integer at any position in arr. Return the minimum number of operations needed to make target a subsequence of arr.

Key Insights

  • A subsequence is formed by deleting elements from an array without changing the order of the remaining elements.
  • The goal is to find how many elements from the target array are already present in arr and in the correct order.
  • The longest increasing subsequence (LIS) can be leveraged to determine how many elements from target can be arranged in arr without additional operations.
  • The minimum operations required will be the difference between the length of target and the length of the longest subsequence found.

Space and Time Complexity

Time Complexity: O(N log N), where N is the length of arr.
Space Complexity: O(N), for storing the index mapping and the dynamic programming array.

Solution

To solve the problem, we can follow these steps:

  1. Create a mapping from each element in the target array to its index. This allows us to quickly check if an element from arr is part of target.
  2. Iterate through arr and build a new list that stores the indices of elements from target that are found in arr.
  3. The longest increasing subsequence (LIS) algorithm can then be applied to this list of indices to find the length of the longest subsequence that can be formed.
  4. The minimum number of operations required will be the difference between the length of target and the length of this longest subsequence.

Code Solutions

def minOperations(target, arr):
    target_indices = {num: i for i, num in enumerate(target)}
    lis = []
    
    for num in arr:
        if num in target_indices:
            index = target_indices[num]
            # Use binary search to find the insertion point
            pos = bisect.bisect_left(lis, index)
            if pos == len(lis):
                lis.append(index)
            else:
                lis[pos] = index
    
    return len(target) - len(lis)
← Back to All Questions