{x}
blog image

Minimum Operations to Make a Subsequence

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. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.

Return the minimum number of operations needed to make target a subsequence of arr.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

 

Example 1:

Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: You can add 5 and 1 in such a way that makes arr = [5,9,4,1,2,3,4], then target will be a subsequence of arr.

Example 2:

Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3

 

Constraints:

  • 1 <= target.length, arr.length <= 105
  • 1 <= target[i], arr[i] <= 109
  • target contains no duplicates.

Solution Explanation: Minimum Operations to Make a Subsequence

This problem asks for the minimum number of operations to make target a subsequence of arr. The key insight is that the minimum number of operations is the difference between the length of target and the length of the longest common increasing subsequence between target and arr. A naive approach of finding the longest common subsequence (LCS) has a time complexity of O(m*n), where 'm' and 'n' are lengths of target and arr respectively, which is inefficient for large inputs.

The optimized solution leverages a Binary Indexed Tree (BIT) to efficiently find the length of the longest increasing subsequence. Here's a breakdown:

1. Preprocessing:

  • A hash map d is created to store the indices of each element in target. This allows for O(1) lookup of an element's position in target.
  • An array nums is created by iterating through arr. Only elements present in d (meaning they also exist in target) are added to nums, and their values are replaced with their indices from target. This transforms the problem into finding the longest increasing subsequence of indices.

2. Longest Increasing Subsequence (LIS) using Binary Indexed Tree:

The core of the solution lies in using a BIT to efficiently find the LIS length. A BIT is a data structure that allows for efficient range maximum queries and updates.

  • BinaryIndexedTree class: This class implements the BIT. update(x, v) updates the BIT to store the maximum value v at index x (and implicitly updates all its ancestors in the BIT). query(x) returns the maximum value from index 1 to x (inclusive).

  • Iterating through nums: The algorithm iterates through nums. For each element x (representing an index in target):

    • v = tree.query(x - 1) + 1: This line performs a range maximum query to find the largest value in the BIT up to x - 1. Adding 1 extends the LIS length.
    • ans = max(ans, v): The current LIS length v is compared to the maximum LIS length found so far (ans).
    • tree.update(x, v): The BIT is updated with the new LIS length v at index x.

3. Result:

Finally, the minimum number of operations is calculated as len(target) - ans, which is the difference between the length of target and the longest common increasing subsequence length found using the BIT.

Time Complexity Analysis:

  • Creating the hash map d: O(m)
  • Creating the array nums: O(n)
  • Iterating through nums and using the BIT: O(n log m). The query and update operations on the BIT take O(log m) time.
  • Overall Time Complexity: O(m + n + n log m) which simplifies to O(n log m) for large inputs, dominated by the BIT operations.

Space Complexity Analysis:

  • Hash map d: O(m)
  • Array nums: O(n) in the worst case (all elements in arr are present in target).
  • Binary Indexed Tree: O(m)
  • Overall Space Complexity: O(m + n)

Code Examples (Python):

The Python code provided previously demonstrates the solution using the BinaryIndexedTree class. The other languages (Java, C++, Go, TypeScript) follow a similar structure with the BinaryIndexedTree class handling BIT operations. The core algorithm remains the same across all languages.