# 1713. Minimum Operations to Make a Subsequence

## Problem Description

The problem presents two integer arrays, `target` and `arr`. The `target` array contains distinct integers, meaning no duplicates. On the other hand, `arr` can contain duplicates and does not necessarily have the same elements or element order as `target`.

The primary goal is to transform the `arr` array into a sequence that contains `target` as a subsequence by performing a certain operation. This operation involves inserting any integer at any position in `arr`. The task is to determine the minimum number of such operations needed to achieve the goal.

A subsequence is defined as a sequence that can be obtained from another sequence by removing some elements without changing the order of the remaining elements. The problem asks for the smallest number of insertions required to make `target` a subsequence of `arr`.

## Intuition

The essential intuition for solving this problem comes from understanding the nature of subsequences and the relationship between the `target` array and the `arr` array. Since the `target` consists of distinct integers, any repeated elements in `arr` do not help us in forming the subsequence and thus do not affect the number of operations required.

The intuition for the solution lies in finding the longest common subsequence between `target` and `arr` and using this to determine the minimum number of operations. However, since the problem asks us to perform insertions to make `target` a subsequence of `arr`, rather than finding a common subsequence of both, we can focus on finding a subsequence in `arr` that matches the order of `target`. The length of this subsequence in `arr` will allow us to calculate the operations needed as `len(target) - len(longest_subsequence_in_arr_matching_target)`.

To find the longest increasing subsequence efficiently, we take advantage of the fact that numbers in `target` are unique, which allows us to assign a unique index to each number in `target`. Then, we process `arr` and transform it into a sequence of indices according to the positions of its elements in `target`. Now the problem becomes finding the length of the longest increasing subsequence in this transformed sequence, which can be done using a segment tree or, as in this code, using a Binary Indexed Tree (BIT), also known as a Fenwick Tree.

The Binary Indexed Tree is used to store information about the longest increasing subsequence efficiently while we iterate through the transformed `arr`. For each element, we find the length of the longest subsequence up to that point and update our tree. After processing all elements, the length of the longest increasing subsequence is known, which gives us the number of elements in `arr` that already form a subsequence with `target`. Subtracting this number from the length of `target` gives us the minimum number of operations needed.

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

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for `[50, 3, 10, 7, 40, 80]` is `4` and LIS is `[3, 7, 40, 80]`.

What is the recurrence relation?

## Solution Approach

The solution uses a Binary Indexed Tree (BIT) to find the length of the Longest Increasing Subsequence (LIS) efficiently, which is a key part in solving this problem.

Here is a step-by-step implementation of the solution:

1. Create a dictionary `d` from elements of `target` to their indices. This serves two purposes. It allows us to check if an element of `arr` is in `target` in constant time and gives us a way to transform elements of `arr` to their corresponding indices in `target`.

2. Create a new list `nums` consisting of the indices in `target` of the elements in `arr`. This transformation helps us to ignore elements in `arr` which are not in `target` and to work with indices rather than values, simplifying the problem to finding an LIS (which indicates the longest subsequence in `arr` that is in order with `target`).

3. Compute the length of the LIS in this new list `nums`. To perform this step:

• We create a BIT class with an update and query operation, where `update(x, val)` will update the tree at index `x` with the value `val`, and `query(x)` retrieves the maximum value from the beginning of the array up to index `x`.
• Then, we sort `nums` to eliminate duplicates and map each element to its index plus one (to avoid 0 index in BIT as the tree is 1-indexed) and create an instance of BIT with the length of this unique elements list.
• Iterate through each element `v` in the original `nums` list (which is a list of indices within `target`), and for each of these, use the BIT to find the longest subsequence up until that point and update the value of that index plus one in the tree with the new length if it's larger than the current value.
4. The length of the LIS is equivalent to the number of operations we don't need to perform. Therefore, we subtract the length of the LIS from the length of `target` to find the minimum number of operations required to make `target` a subsequence of `arr`.

By understanding the definition of a subsequence and using the efficient updates and queries of a Binary Indexed Tree to track the length of the longest subsequence, the implementation solves the problem with a time complexity of `O(N log N)`, where N is the length of `arr`.

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

Which data structure is used to implement priority queue?

### Example Walkthrough

Let's work through a small example to illustrate the solution approach:

Suppose we are given the following input:

• `target = [5, 1, 3]`
• `arr = [3, 5, 3, 1, 3, 5]`

Here's the step-by-step process:

1. Creating the dictionary: We map each element in `target` to its index:

• `d = {5: 0, 1: 1, 3: 2}`
2. Transforming `arr` into indices: Using the dictionary `d`, we convert `arr` to a sequence of indices based on `target` (ignoring elements not found in `target`):

• `nums = [2, 0, 2, 1, 2, 0]`
3. Computing the LIS:

• Initialize a Binary Indexed Tree to help us compute the LIS.
• Process the transformed `nums`. As we iterate over `nums`, for each element `v = nums[i]`, we find the length of the longest subsequence that we can achieve up to the current index.
• Update the BIT with the new LIS length at the index corresponding to `v` if it's larger than the current recorded length.

For our example `nums = [2, 0, 2, 1, 2, 0]`, let's see how the Binary Indexed Tree updates:

• Initially, the BIT is all zeroes: `BIT = [0, 0, 0]`
• We process the first element `2`: `BIT = [0, 0, 1]` (longest subsequence ending in index `2` is of length `1`)
• Process `0`: `BIT = [1, 0, 1]` (subsequence of length `1` ending in index `0`)
• Process the second `2`: `BIT` remains the same, as `2` does not add to the longest subsequence when coming after `0`
• Process `1`: `BIT = [1, 2, 1]` (subsequence of length `2` can be formed by [3 (index 0), 1 (index 1)])
• Continue with the rest of the elements...

By the end of this process, the BIT's entry for index `2` (which is the largest index) will reflect the length of the LIS of our `nums` sequence. It turns out that our example has a longest subsequence `[0, 1]` or `[5, 1]` in terms of the original `target` array, which has a length of `2`.

1. Calculating Minimum Operations: Finally, we determine the minimum insertions needed:
• `minimum_operations = len(target) - LIS_length`
• `minimum_operations = 3 - 2 = 1`

Thus, the minimum number of operations required to make `target` a subsequence of `arr` is one insertion.

In our example, we could insert the number `1` at the beginning or end of the `arr` to make `target` a subsequence of `arr`:

• Insert `1` at the beginning: `[1, 3, 5, 3, 1, 3, 5]` -> `[1, - (ignored), 5, 1, 3]`
• Insert `1` at the end is unnecessary since `target` is already a subsequence of `arr`.

This illustrates how using indices and a BIT can efficiently solve the problem of finding the minimum number of insertions to make one array a subsequence of another.

## Solution Implementation

``````1from typing import List
2
3class BinaryIndexedTree:
4    def __init__(self, size):
5        self.size = size
6        self.tree_array = [0] * (size + 1)
7
8    @staticmethod
9    def lowbit(index):
10        # Calculate the least significant bit (LSB)
11        return index & -index
12
13    def update(self, index, val):
14        # Update the tree with the value 'val'
15        while index <= self.size:
16            # Maintain the maximum value in the path
17            self.tree_array[index] = max(self.tree_array[index], val)
18            # Move to next index to be updated
19            index += BinaryIndexedTree.lowbit(index)
20
21    def query(self, index):
22        max_val = 0
23        while index:
24            # Find max value up to the 'index'
25            max_val = max(max_val, self.tree_array[index])
26            # Move to parent index
27            index -= BinaryIndexedTree.lowbit(index)
28        return max_val
29
30
31class Solution:
32    def minOperations(self, target: List[int], arr: List[int]) -> int:
33        # Map each target value to its index
34        index_mapping = {value: idx for idx, value in enumerate(target)}
35        # Filter and map the values in 'arr' using the index_mapping
36        mapped_nums = [index_mapping[value] for value in arr if value in index_mapping]
37        # Calculate and return the min number of operations
38        return len(target) - self.lengthOfLIS(mapped_nums)
39
40    def lengthOfLIS(self, nums: List[int]) -> int:
41        # Create a sorted list of unique values from 'nums'
42        unique_sorted_nums = sorted(set(nums))
43        # Map each value to its index (+1 to avoid zero index)
44        index_mapping = {value: idx for idx, value in enumerate(unique_sorted_nums, 1)}
45        tree = BinaryIndexedTree(len(index_mapping))
46        longest_increasing_subsequence = 0
47        for value in nums:
48            # Map the value to its corresponding index in the tree
49            mapped_index = index_mapping[value]
50            # Find the length of LIS ending with 'value'
51            current_lis = tree.query(mapped_index - 1) + 1
52            # Update the maximum length found so far
53            longest_increasing_subsequence = max(longest_increasing_subsequence, current_lis)
54            # Update the tree with the new length
55            tree.update(mapped_index, current_lis)
56        # Return the length of the longest increasing subsequence
57        return longest_increasing_subsequence
58``````
``````1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5import java.util.TreeSet;
6
7// Class representing a Binary Indexed Tree (also known as a Fenwick Tree)
8class BinaryIndexedTree {
9    private int size; // The size of the array
10    private int[] tree; // The array representation of the tree
11
12    // Constructor initializes the tree with a specified size
13    public BinaryIndexedTree(int size) {
14        this.size = size;
15        this.tree = new int[size + 1];
16    }
17
18    // Method to calculate the lowest one bit of an integer
19    public static int lowbit(int x) {
20        return x & -x;
21    }
22
23    // Method to update the tree with a new value at a specific index
24    public void update(int index, int val) {
25        while (index <= size) {
26            tree[index] = Math.max(tree[index], val);
27            index += lowbit(index);
28        }
29    }
30
31    // Method to query the maximum value in the tree up to a certain index
32    public int query(int index) {
33        int maxVal = 0;
34        while (index > 0) {
35            maxVal = Math.max(maxVal, tree[index]);
36            index -= lowbit(index);
37        }
38        return maxVal;
39    }
40}
41
42// Solution class containing methods to solve the minimum operations problem
43class Solution {
44    // Method that returns the minimum number of operations to make one array a subsequence of another
45    public int minOperations(int[] target, int[] arr) {
46        Map<Integer, Integer> valueToIndex = new HashMap<>();
47        for (int i = 0; i < target.length; ++i) {
48            valueToIndex.put(target[i], i);
49        }
50        List<Integer> indices = new ArrayList<>();
51        for (int value : arr) {
52            if (valueToIndex.containsKey(value)) {
54            }
55        }
56        return target.length - lengthOfLIS(indices);
57    }
58
59    // Private method that computes the length of the Longest Increasing Subsequence (LIS)
60    private int lengthOfLIS(List<Integer> nums) {
61        TreeSet<Integer> orderedSet = new TreeSet<>();
62        for (int v : nums) {
64        }
65        int idx = 1;
66        Map<Integer, Integer> valueToTreeIndex = new HashMap<>();
67        for (int v : orderedSet) {
68            valueToTreeIndex.put(v, idx++);
69        }
70        int lisLength = 0;
71        BinaryIndexedTree tree = new BinaryIndexedTree(nums.size());
72        for (int v : nums) {
73            int x = valueToTreeIndex.get(v);
74            int len = tree.query(x - 1) + 1;
75            lisLength = Math.max(lisLength, len);
76            tree.update(x, len);
77        }
78        return lisLength;
79    }
80}
81``````
``````1#include <vector>
2#include <unordered_map>
3#include <set>
4using namespace std;
5
6class BinaryIndexedTree {
7public:
8    int size;
9    vector<int> tree;
10
11    // Constructor initializes the tree
12    BinaryIndexedTree(int size)
13        : size(size), tree(size + 1) {}
14
15    // Update function applies the given value using the max operation
16    void update(int index, int val) {
17        while (index <= size) {
18            tree[index] = max(tree[index], val);
19            index += lowBit(index);
20        }
21    }
22
23    // Query function finds the maximum value up to the given index
24    int query(int index) {
25        int result = 0;
26        while (index > 0) {
27            result = max(result, tree[index]);
28            index -= lowBit(index);
29        }
30        return result;
31    }
32
33    // Helper function to calculate the lowest set bit (important for BIT operations)
34    int lowBit(int x) {
35        return x & -x;
36    }
37};
38
39class Solution {
40public:
41    // Function to calculate the minimum operations needed to make target a subsequence of arr
42    int minOperations(vector<int>& target, vector<int>& arr) {
43        unordered_map<int, int> indexMap;
44
45        // Mapping each element of target to its index
46        for (int i = 0; i < target.size(); ++i) {
47            indexMap[target[i]] = i;
48        }
49
50        // Creating a list of indices of elements in arr that are found in target
51        vector<int> relevantIndices;
52        for (int num : arr) {
53            if (indexMap.count(num)) {
54                relevantIndices.push_back(indexMap[num]);
55            }
56        }
57
58        // The result is the size of target minus the length of the longest increasing subsequence of relevant indices
59        return target.size() - lengthOfLIS(relevantIndices);
60    }
61
62    // Function to find the length of the longest increasing subsequence using a Binary Indexed Tree
63    int lengthOfLIS(vector<int>& nums) {
64        set<int> sortedNums(nums.begin(), nums.end());
65        int index = 1;
66        unordered_map<int, int> indexMap;
67
68        // Create a mapping from each number to its rank in the sorted set
69        for (int value : sortedNums) {
70            indexMap[value] = index++;
71        }
72
73        // Using Binary Indexed Tree to keep track of the longest increasing subsequence dynamically
74        BinaryIndexedTree bit(indexMap.size());
75        int maxLength = 0;
76        for (int num : nums) {
77            int currentIndex = indexMap[num];
78            int currentLength = bit.query(currentIndex - 1) + 1;
79            maxLength = max(maxLength, currentLength);
80            bit.update(currentIndex, currentLength);
81        }
82        return maxLength;
83    }
84};
85``````
``````1// Import the necessary libraries for collections and algorithm
2import { max } from 'lodash';
3
4// TypeScript doesn't have a built-in max function, you could use Math.max or a utility library like lodash.
5
6// Initialize the size of the Binary Indexed Tree and the tree structure as an array
7let size: number;
8let tree: number[];
9
10// Function to initialize the Binary Indexed Tree
11function initializeBIT(newSize: number) {
12  size = newSize;
13  tree = Array(newSize + 1).fill(0);
14}
15
16// Function to update a value in the Binary Indexed Tree using max operation
17function update(index: number, val: number): void {
18  while (index <= size) {
19    tree[index] = max([tree[index], val]);
20    index += lowBit(index);
21  }
22}
23
24// Function to query the maximum value in the Binary Indexed Tree up to a given index
25function query(index: number): number {
26  let result = 0;
27  while (index > 0) {
28    result = max([result, tree[index]]);
29    index -= lowBit(index);
30  }
31  return result;
32}
33
34// Helper function for Binary Indexed Tree to calculate the lowest set bit
35function lowBit(x: number): number {
36  return x & -x;
37}
38
39// Function to calculate the minimum number of operations needed to make the target a subsequence of arr
40function minOperations(target: number[], arr: number[]): number {
41  let indexMap: Map<number, number> = new Map<number, number>();
42
43  // Map each element of target to its index
44  target.forEach((num, index) => indexMap.set(num, index));
45
46  // Create a list of indices in arr that are present in target
47  let relevantIndices: number[] = arr
48    .filter(num => indexMap.has(num))
49    .map(num => indexMap.get(num)!);
50
51  // Deduce the result from the size of target and the length of the longest increasing subsequence of relevantIndices
52  return target.length - lengthOfLIS(relevantIndices);
53}
54
55// Function to find the length of the longest increasing subsequence (LIS)
56function lengthOfLIS(nums: number[]): number {
57  let sortedNums = Array.from(new Set(nums)).sort((a, b) => a - b);
58  let index = 1;
59  let indexMap: Map<number, number> = new Map<number, number>();
60
61  // Map each number to its rank in the sorted list
62  sortedNums.forEach(value => indexMap.set(value, index++));
63
64  // Initialize the Binary Indexed Tree for tracking the longest increasing subsequence dynamically
65  initializeBIT(indexMap.size);
66  let maxLength = 0;
67
68  // Calculate the LIS using the Binary Indexed Tree
69  nums.forEach(num => {
70    let currentIndex = indexMap.get(num)!;
71    let currentLength = query(currentIndex - 1) + 1;
72    maxLength = max([maxLength, currentLength]);
73    update(currentIndex, currentLength);
74  });
75
76  return maxLength;
77}
78``````
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the minimum element can be found in:

## Time and Space Complexity

### Time Complexity

The time complexity of this solution is analyzed as follows:

• Constructing a dictionary `d` from `target` has a time complexity of `O(N)` where `N` is the length of `target`.
• Filtering `arr` to create `nums` using dictionary `d` has a time complexity of `O(M)` where `M` is the length of `arr`.
• So far, the overall time complexity is `O(N + M)`.
• Sorting the unique values of `nums` has a time complexity of `O(P log P)` where `P` is the number of unique values in `nums`.
• Then, creating a mapping `m` is an `O(P)` operation.
• The `lengthOfLIS` involves iterating over all elements in `nums` and making use of Binary Indexed Tree operations (query and update), which has `O(log P)` complexity for each call.
• As it does this for every one of the `K` numbers in `nums`, this part contributes an `O(K log P)` complexity.

Thus, the overall time complexity of the solution is `O(N + M + P log P + K log P)`.

Note: Since the Binary Indexed Tree has a size equal to the amount of unique elements in the `nums` array and all values are mapped to a continuous range, `P` is the upper-bound for `K` as well, and therefore `O(K log P)` can be considered as `O(P log P)` in worst case scenario.

### Space Complexity

The space complexity is calculated based on the data structures used:

• The dictionary `d` and mapping `m` both store at most `N` and `P` elements respectively, contributing `O(N)` and `O(P)` space.
• The Binary Indexed Tree (`c` array) has a length of `P + 1`, providing an additional `O(P)` space complexity.
• The transformed array `nums` which stores filtered and mapped values from `arr` based on `target` contributes an `O(M)` space requirement.

Therefore, the overall space complexity of the solution is `O(N + P + M)` with `P <= N <= M` generally.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?