# Minimize insertions and deletions in given array A[] to make it identical to array B[]

Given two arrays **A[]** and **B[]** of length **N** and **M** respectively, the task is to find the minimum number of insertions and deletions on the array **A[]**, required to make both the arrays identical.**Note: **Array **B[]** is sorted and all its elements are distinct, operations can be performed at any index not necessarily at the end.

**Example:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:A[] = {1, 2, 5, 3, 1}, B[] = {1, 3, 5}Output:4Explanation:In 1st operation, delete A[1] from array A[] and in 2nd operation, insert 3 at that position. In 3rd and 4th operation, delete A[3] and A[4]. Hence, A[] = {1, 3, 5} = B[] in 4 operations which is the minimum possible.

Input:A[] = {1, 4}, B[] = {1, 4}Output:0

**Approach: **The given problem can be solved by observing the fact that the most optimal choice of elements that must not be deleted from the array **A[]** are the elements of the Longest Increasing Subsequence among the common elements in **A[]** and **B[]**. Therefore, the above problem can be solved by storing the common elements of the array **A[]** and **B[]** in a vector and finding the LIS using this algorithm. Thereafter, all the elements other than that of LIS can be deleted from **A[]**, and the remaining elements that are in **B[]** but not in **A[]** can be inserted.

Below is the implementation of the above approach:

## C++

`// C++ program of the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find minimum operations` `// to convert array A to B using` `// insertions and deletion opertations` `int` `minInsAndDel(` `int` `A[], ` `int` `B[], ` `int` `n, ` `int` `m)` `{` ` ` `// Stores the common elements in A and B` ` ` `vector<` `int` `> common;` ` ` `unordered_set<` `int` `> s;` ` ` `// Loop to iterate over B` ` ` `for` `(` `int` `i = 0; i < m; i++) {` ` ` `s.insert(B[i]);` ` ` `}` ` ` `// Loop to iterate over A` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `// If current element is also present` ` ` `// in array B` ` ` `if` `(s.find(A[i]) != s.end()) {` ` ` `common.push_back(A[i]);` ` ` `}` ` ` `}` ` ` `// Stores the Longest Increasing Subsequence` ` ` `// among the common elements in A and B` ` ` `vector<` `int` `> lis;` ` ` `// Loop to find the LIS among the common` ` ` `// elements in A and B` ` ` `for` `(` `auto` `e : common) {` ` ` `auto` `it = lower_bound(` ` ` `lis.begin(), lis.end(), e);` ` ` `if` `(it != lis.end())` ` ` `*it = e;` ` ` `else` ` ` `lis.push_back(e);` ` ` `}` ` ` `// Stores the final answer` ` ` `int` `ans;` ` ` `// Count of elements to be inserted in A[]` ` ` `ans = m - lis.size();` ` ` `// Count of elements to be deleted from A[]` ` ` `ans += n - lis.size();` ` ` `// Return Answer` ` ` `return` `ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 5, M = 3;` ` ` `int` `A[] = { 1, 2, 5, 3, 1 };` ` ` `int` `B[] = { 1, 3, 5 };` ` ` `cout << minInsAndDel(A, B, N, M) << endl;` ` ` `return` `0;` `}` |

## Java

`/*package whatever //do not write package name here */` `import` `java.util.*;` `class` `GFG` `{` ` ` ` ` `// Function to implement lower_bound` `static` `int` `lower_bound(` `int` `arr[], ` `int` `X)` `{` ` ` `int` `mid;` ` ` `int` `N = arr.length;` ` ` ` ` `// Initialise starting index and` ` ` `// ending index` ` ` `int` `low = ` `0` `;` ` ` `int` `high = N;` ` ` ` ` `// Till low is less than high` ` ` `while` `(low < high) {` ` ` `mid = low + (high - low) / ` `2` `;` ` ` ` ` `// If X is less than or equal` ` ` `// to arr[mid], then find in` ` ` `// left subarray` ` ` `if` `(X <= arr[mid]) {` ` ` `high = mid;` ` ` `}` ` ` ` ` `// If X is greater arr[mid]` ` ` `// then find in right subarray` ` ` `else` `{` ` ` `low = mid + ` `1` `;` ` ` `}` ` ` `}` ` ` ` ` `// if X is greater than arr[n-1]` ` ` `if` `(low < N && arr[low] < X) {` ` ` `low++;` ` ` `}` ` ` ` ` `// Return the lower_bound index` ` ` `return` `low;` `}` ` ` ` ` `// Function to find minimum operations` ` ` `// to convert array A to B using` ` ` `// insertions and deletion opertations` ` ` `static` `int` `minInsAndDel(` `int` `A[], ` `int` `B[], ` `int` `n, ` `int` `m)` ` ` `{` ` ` `// Stores the common elements in A and B` ` ` `int` `[] common = ` `new` `int` `[n];` ` ` `int` `k = ` `0` `;` ` ` `HashSet<Integer> s= ` `new` `HashSet<Integer>();` ` ` `// Loop to iterate over B` ` ` `for` `(` `int` `i = ` `0` `; i < m; i++) {` ` ` `s.add(B[i]);` ` ` `}` ` ` `// Loop to iterate over A` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `// If current element is also present` ` ` `// in array B` ` ` `if` `(s.contains(A[i]) == ` `false` `) {` ` ` `common[k++] = A[i];` ` ` `}` ` ` `}` ` ` `// Stores the Longest Increasing Subsequence` ` ` `// among the common elements in A and B` ` ` `int` `[] lis = ` `new` `int` `[n];` ` ` `k = ` `0` `;` ` ` `ArrayList<Integer> LIS = ` `new` `ArrayList<Integer>();` ` ` ` ` `// Loop to find the LIS among the common` ` ` `// elements in A and B` ` ` `for` `(` `int` `e : common) {` ` ` `int` `it = lower_bound(lis, e);` ` ` `if` `(it <lis.length)` ` ` `it = e;` ` ` `else` `{` ` ` `lis[k++] = e;` ` ` `LIS.add(e);` ` ` `}` ` ` `}` ` ` `// Stores the final answer` ` ` `int` `ans;` ` ` `// Count of elements to be inserted in A[]` ` ` `ans = m - LIS.size()-` `1` `;` ` ` `// Count of elements to be deleted from A[]` ` ` `ans = ans+ n - LIS.size()-` `1` `;` ` ` `// Return Answer` ` ` `return` `ans;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `N = ` `5` `, M = ` `3` `;` ` ` `int` `A[] = { ` `1` `, ` `2` `, ` `5` `, ` `3` `, ` `1` `};` ` ` `int` `B[] = { ` `1` `, ` `3` `, ` `5` `};` ` ` `System.out.println(minInsAndDel(A, B, N, M));` ` ` `}` `}` `// This code is contributed by lokeshpotta20.` |

## Python3

`# python program of the above approach` `from` `bisect ` `import` `bisect_left` `# Function to find minimum operations` `# to convert array A to B using` `# insertions and deletion opertations` `def` `minInsAndDel(A, B, n, m):` ` ` `# Stores the common elements in A and B` ` ` `common ` `=` `[]` ` ` `s ` `=` `set` `()` ` ` `# Loop to iterate over B` ` ` `for` `i ` `in` `range` `(` `0` `, m):` ` ` `s.add(B[i])` ` ` `# Loop to iterate over A` ` ` `for` `i ` `in` `range` `(` `0` `, n):` ` ` `# If current element is also present` ` ` `# in array B` ` ` `if` `(A[i] ` `in` `s):` ` ` `common.append(A[i])` ` ` `# Stores the Longest Increasing Subsequence` ` ` `# among the common elements in A and B` ` ` `lis ` `=` `[]` ` ` `# Loop to find the LIS among the common` ` ` `# elements in A and B` ` ` `for` `e ` `in` `common:` ` ` `it ` `=` `bisect_left(lis, e, ` `0` `, ` `len` `(lis))` ` ` `if` `(it !` `=` `len` `(lis)):` ` ` `lis[it] ` `=` `e` ` ` `else` `:` ` ` `lis.append(e)` ` ` `# Stores the final answer` ` ` `ans ` `=` `0` ` ` `# Count of elements to be inserted in A[]` ` ` `ans ` `=` `m ` `-` `len` `(lis)` ` ` `# Count of elements to be deleted from A[]` ` ` `ans ` `+` `=` `n ` `-` `len` `(lis)` ` ` `# Return Answer` ` ` `return` `ans` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `N ` `=` `5` ` ` `M ` `=` `3` ` ` `A ` `=` `[` `1` `, ` `2` `, ` `5` `, ` `3` `, ` `1` `]` ` ` `B ` `=` `[` `1` `, ` `3` `, ` `5` `]` ` ` `print` `(minInsAndDel(A, B, N, M))` ` ` `# This code is contributed by rakeshsahni` |

## C#

`/*package whatever //do not write package name here */` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG {` ` ` `// Function to implement lower_bound` ` ` `static` `int` `lower_bound(` `int` `[] arr, ` `int` `X)` ` ` `{` ` ` `int` `mid;` ` ` `int` `N = arr.Length;` ` ` `// Initialise starting index and` ` ` `// ending index` ` ` `int` `low = 0;` ` ` `int` `high = N;` ` ` `// Till low is less than high` ` ` `while` `(low < high) {` ` ` `mid = low + (high - low) / 2;` ` ` `// If X is less than or equal` ` ` `// to arr[mid], then find in` ` ` `// left subarray` ` ` `if` `(X <= arr[mid]) {` ` ` `high = mid;` ` ` `}` ` ` `// If X is greater arr[mid]` ` ` `// then find in right subarray` ` ` `else` `{` ` ` `low = mid + 1;` ` ` `}` ` ` `}` ` ` `// if X is greater than arr[n-1]` ` ` `if` `(low < N && arr[low] < X) {` ` ` `low++;` ` ` `}` ` ` `// Return the lower_bound index` ` ` `return` `low;` ` ` `}` ` ` `// Function to find minimum operations` ` ` `// to convert array A to B using` ` ` `// insertions and deletion opertations` ` ` `static` `int` `minInsAndDel(` `int` `[] A, ` `int` `[] B, ` `int` `n, ` `int` `m)` ` ` `{` ` ` `// Stores the common elements in A and B` ` ` `int` `[] common = ` `new` `int` `[n];` ` ` `int` `k = 0;` ` ` `HashSet<` `int` `> s = ` `new` `HashSet<` `int` `>();` ` ` `// Loop to iterate over B` ` ` `for` `(` `int` `i = 0; i < m; i++) {` ` ` `s.Add(B[i]);` ` ` `}` ` ` `// Loop to iterate over A` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `// If current element is also present` ` ` `// in array B` ` ` `if` `(s.Contains(A[i]) == ` `false` `) {` ` ` `common[k++] = A[i];` ` ` `}` ` ` `}` ` ` `// Stores the Longest Increasing Subsequence` ` ` `// among the common elements in A and B` ` ` `int` `[] lis = ` `new` `int` `[n];` ` ` `k = 0;` ` ` `List<` `int` `> LIS = ` `new` `List<` `int` `>();` ` ` `// Loop to find the LIS among the common` ` ` `// elements in A and B` ` ` `foreach` `(` `int` `e ` `in` `common)` ` ` `{` ` ` `int` `it = lower_bound(lis, e);` ` ` `if` `(it < lis.Length)` ` ` `it = e;` ` ` `else` `{` ` ` `lis[k++] = e;` ` ` `LIS.Add(e);` ` ` `}` ` ` `}` ` ` `// Stores the final answer` ` ` `int` `ans;` ` ` `// Count of elements to be inserted in A[]` ` ` `ans = m - LIS.Count - 1;` ` ` `// Count of elements to be deleted from A[]` ` ` `ans = ans + n - LIS.Count - 1;` ` ` `// Return Answer` ` ` `return` `ans;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(` `string` `[] args)` ` ` `{` ` ` `int` `N = 5, M = 3;` ` ` `int` `[] A = { 1, 2, 5, 3, 1 };` ` ` `int` `[] B = { 1, 3, 5 };` ` ` `Console.WriteLine(minInsAndDel(A, B, N, M));` ` ` `}` `}` `// This code is contributed by ukasp.` |

## Javascript

`<script>` `// Javascript program of the above approach` `// Function to find minimum operations` `// to convert array A to B using` `// insertions and deletion opertations` `function` `minInsAndDel(A, B, n, m) {` ` ` `// Stores the common elements in A and B` ` ` `let common = [];` ` ` `let s = ` `new` `Set();` ` ` `// Loop to iterate over B` ` ` `for` `(let i = 0; i < m; i++) {` ` ` `s.add(B[i]);` ` ` `}` ` ` `// Loop to iterate over A` ` ` `for` `(let i = 0; i < n; i++) {` ` ` `// If current element is also present` ` ` `// in array B` ` ` `if` `(s.has(A[i])) {` ` ` `common.push(A[i]);` ` ` `}` ` ` `}` ` ` `// Stores the Longest Increasing Subsequence` ` ` `// among the common elements in A and B` ` ` `let lis = [];` ` ` `// Loop to find the LIS among the common` ` ` `// elements in A and B` ` ` `for` `(e of common) {` ` ` `let it = lower_bound(lis, lis.length, e);` ` ` `if` `(lis.includes(it))` ` ` `it = e;` ` ` `else` ` ` `lis.push(e);` ` ` `}` ` ` `// Stores the final answer` ` ` `let ans;` ` ` `// Count of elements to be inserted in A[]` ` ` `ans = m - lis.length;` ` ` `// Count of elements to be deleted from A[]` ` ` `ans += n - lis.length;` ` ` `// Return Answer` ` ` `return` `ans;` `}` `function` `lower_bound(arr, N, X)` `{` ` ` `let mid;` ` ` `// Initialise starting index and` ` ` `// ending index` ` ` `let low = 0;` ` ` `let high = N;` ` ` `// Till low is less than high` ` ` `while` `(low < high) {` ` ` `mid = Math.floor(low + (high - low) / 2);` ` ` `// If X is less than or equal` ` ` `// to arr[mid], then find in` ` ` `// left subarray` ` ` `if` `(X <= arr[mid]) {` ` ` `high = mid;` ` ` `}` ` ` `// If X is greater arr[mid]` ` ` `// then find in right subarray` ` ` `else` `{` ` ` `low = mid + 1;` ` ` `}` ` ` `}` ` ` `// if X is greater than arr[n-1]` ` ` `if` `(low < N && arr[low] < X) {` ` ` `low++;` ` ` `}` ` ` `// Return the lower_bound index` ` ` `return` `low;` `}` `// Driver Code` `let N = 5, M = 3;` `let A = [1, 2, 5, 3, 1];` `let B = [1, 3, 5];` `document.write(minInsAndDel(A, B, N, M));` `// This code is contributed by saurabh_jaiswal.` `</script>` |

**Output**

4

**Time Complexity:** O(N*log N)**Auxiliary Space:** O(N)