Minimum insertions.

The idea here is to insert every integer of ‘arr1’ at every possible position in the ‘arr2’. After inserting all the elements of ‘arr1’ in ‘arr2’, ‘arr1’ will become a subsequence of ‘arr2’. Out of all such series of insertions, we will take the one with the minimum number of insertions.

Algorithm:

• Declare an integer, say ‘minInsertions’, to store the minimum number of integers that need to be inserted into ‘arr2’ to make ‘arr1’ a subsequence of  ‘arr2’.
• Call the ‘allInsertions’ function with ‘arr1‘, ‘arr2’, 0, 0, ‘N’, and ‘M’ as arguments, and store its returned value into ‘minInsertions’.
• Return ‘minInsertions’.

Description of ‘allInsertions’ function

This function is used to insert all the elements of  ‘arr1’ from ‘low1’ to ‘N’ - 1  inclusive into every possible position from ‘low2’ to ‘M’ - 1 inclusive, in ‘arr2’.

This function will take six parameters :

• arr1: An array of ‘N’ integers given in the problem.
• arr2: An array of ‘M’ integers given in the problem.
• low1: An integer denoting the starting index of ‘arr1’
• low2: An integer denoting the starting index of ‘arr2’
• N: An integer denoting the number of elements in ‘arr1’
• M: An integer denoting the number of elements in ‘arr2’

int allInsertions(arr1, arr2, low1, low2, N, M):

• If ‘low1’ equals ‘N’.
  • Return 0, as we don’t have any element in ‘arr1’ to insert in ‘arr2’.
• If ‘low2’ equals ‘M’.
  • Return (N - low1), as this number of elements, needs to be inserted in ‘arr2’ to make ‘arr1’ a subsequence.
• Declare a variable to keep track of the optimal insertions, say ‘answer’.
• If ‘arr1[low1]’ is the same as ‘arr2[low2]’:
  • This means that ‘arr1[low1]’ is already present in ‘arr2’
  • Recursively call the ‘allInsertions’ function with ‘arr1‘, ‘arr2’, low1 + 1, low2 + 1, ‘N’, and ‘M’ as arguments, and store its returned value into ‘answer’.
• Else:
  • Otherwise, we will insert ‘arr1[low1]’ in ‘arr2’ at ‘low2’.
  • Recursively call the ‘allInsertions’ function with ‘arr1‘, ‘arr2’, low1 + 1, low2, ‘N’, and ‘M’ as arguments, and store its returned value into ‘answer’.
  • Increment ‘answer’ as we have inserted an element in ‘arr2’, i.e., do ‘answer’ = answer + 1.
• As we need to make ‘arr1’ a subsequence of ‘arr2’ we can skip the current position of ‘arr2’ and try to insert ‘arr1[low1]’ in some higher positions.
• Recursively call the ‘allInsertions’ function with ‘arr1‘, ‘arr2’, low1, low2 + 1, ‘N’, and ‘M’ as arguments, and store its returned value into a variable, say ‘currAnswer’.
• Update ‘answer’ as the minimum of ‘answer’ and ‘currAnswer’.
• Return ‘answer’.

The idea here is to optimize the previous approach using dynamic programming. We are calling some functions, again and again, so we will call them once and store their values in a ‘dp’ array.

The below diagram shows that ‘allInsertions’ are called multiple times for ‘arr1’ = {1, 2, 3} and ‘arr2’ = {2, 1, 3}, hence there are overlapping subproblems.

Algorithm:

• Declare a 2 - Dimensional array of integers, say ‘dp’ of size N * M, to store the answer for each subproblem in the ‘allInsertions’ function and initialize it with -1.
• Declare an integer, say ‘minInsertions’, to store the minimum number of integers that need to be inserted into ‘arr2’ to make ‘arr1’ a subsequence of  ‘arr2’.
• Call the ‘allInsertions’ function with ‘arr1‘, ‘arr2’, 0, 0, ‘N’, ‘M’, and ‘dp’ as arguments, and store its returned value into ‘minInsertions’.
• Return ‘minInsertions’.

Description of ‘allInsertions’ function

This function is used to insert all the elements of  ‘arr1’ from ‘low1’ to ‘N’ - 1  inclusive, into every possible position from ‘low2’ to ‘M’ - 1 inclusive, in ‘arr2’.

This function will take seven parameters :

• arr1: An array of ‘N’ integers given in the problem.
• arr2: An array of ‘M’ integers given in the problem.
• low1: An integer denoting the starting index of ‘arr1’
• low2: An integer denoting the starting index of ‘arr2’
• N: An integer denoting the number of elements in ‘arr1’
• M: An integer denoting the number of elements in ‘arr2’
• dp: A 2 - Dimensional array of integers to store the answers of each subproblem.

int allInsertions(arr1, arr2, low1, low2, N, M, dp):

• If ‘low1’ equals ‘N’
  • Return 0, as we don’t have any element in ‘arr1’ to insert in ‘arr2’.
• If ‘low2’ equals ‘M’
  • Return (N - low1), as this number of elements, needs to be inserted in ‘arr2’ to make ‘arr1’ a subsequence.
• If ‘dp[low1][low2]’ not equals -1
  • return ‘dp[low1][low2]’, as the answer to this subproblem is already calculated, and we’ll just reuse the computed answer.
• Declare a variable to keep track of the optimal insertions, say ‘answer’.
• If ‘arr1[low1]’ is the same as  ‘arr2[low2]’
  • This means that ‘arr1[low1]’ is already present in ‘arr2’
  • Recursively call the ‘allInsertions’ function with ‘arr1‘, ‘arr2’, low1 + 1, low2 + 1, ‘N’, ‘M’, and ‘dp’ as arguments, and store its returned value into ‘answer’.
• Else
  • Otherwise, we will insert ‘arr1[low1]’ in ‘arr2’.
  • Recursively call the ‘allInsertions’ function with ‘arr1‘, ‘arr2’, low1 + 1, low2, ‘N’, ‘M’, and ‘dp’ as arguments, and store its returned value into ‘answer’.
  • Increment ‘answer’ as we have inserted an element in ‘arr2’, i.e., do ‘answer’ = answer + 1.
• As we need to make ‘arr1’ a subsequence of ‘arr2’ we can skip the current position of ‘arr2’ and try to insert ‘arr1[low1]’ in some higher positions.
• Recursively call the ‘allInsertions’ function with ‘arr1‘, ‘arr2’, low1, low2 + 1, ‘N’, ‘M’,  and ‘dp’ as arguments, and store its returned value into a variable, say ‘currAnswer’.
• Update ‘answer’ as the minimum of ‘answer’ and ‘currAnswer’.
• Store the computed answer in the dp table, i.e., do ‘dp[low1][low2]’  = answer.
• Return ‘answer’.

The idea here is to use the fact that ‘arr1’ contains all distinct elements. We will do a one-to-one mapping between all the elements of ‘arr2’ and ‘arr1’ in such a way that for any i-th element of ‘arr2’ if ‘arr2[i]’ is not present in ‘arr1’ we will simply ignore this element, otherwise, we will map ‘arr2[i]’ with the index of ‘arr2[i]’ in ‘arr1’ and store this index into an array of integers, say ‘mappingIndex’. Now, we will find the length of the longest increasing subsequence of ‘mappingIndex’. The length of the longest increasing subsequence of ‘mappingIndex’ will basically be the length of the longest common subsequence between ‘arr1’ and ‘arr2’. Therefore, we need to insert (‘N’ - length of the longest common subsequence between ‘arr1’ and ‘arr2’) number of elements in ‘arr2’ to make ‘arr1’ a subsequence. 

Algorithm:

• Declare a hashmap, say ‘hashMap’ to store the index of each element in ‘arr1’.
• Run a loop for ‘i’ from ‘0’ to ‘N’ - 1
  • Store ‘i’ as the index of ‘arr1[i]’ in ‘hashMap’, i.e. do ‘hashMap[arr1[i]]’ = i.
• Declare an array of integers, say ‘mappingIndex’, to store the index of elements of ‘arr2’ that are present in ‘arr1’.
• Run a loop for ‘i’ from 0 to ‘M’ - 1
  • If ‘arr2[i]’ is present in ‘arr1’
    • Insert the index of ‘arr2[i]’ in ‘arr1’ into ‘mappingIndex’, i.e. insert ‘hashMap[arr2[i]]’ in ‘mappingIndex’.
• Declare an array of integers, say ‘LIS’, to store the longest increasing subsequence of ‘mappingIndex’.
• Run a loop for ‘i’ from 0 to size of ‘mappingIndex’ - 1
  • Find the index of the element in ‘LIS’ such that it is greater than or equal to ‘mappingIndex[i]’ and has the lowest index possible by using a lower bound on ‘LIS’.
  • If no such index exists:
    • Insert ‘mappingIndex[i]’ in ‘LIS’.
  • Else:
    • Update the element of that index as the minimum of itself and ‘mappingIndex[i]’.
• Declare an integer, say ‘lengthLIS’, to store the length of the longest increasing subsequence of ‘mappingIndex’ and initialize it with the size of ‘LIS’.
• Return (‘N’ - ‘lengthLIS’), as this is the minimum number of elements that we need to insert in ‘arr2’ to make ‘arr1’ a subsequence.

The idea here is to use the fact that ‘arr1’ contains all distinct elements. We will do a one-to-many mapping between all the elements of ‘arr1’ to its corresponding elements in ‘arr2’. We will create an array of integers, say ‘dp’ of size ‘M’, where ‘dp[i]’ will denote the length of the longest common subsequence between ‘arr1’ and ‘arr2[0 . . . i ]’, and ending at ‘i’. Now, for any i-th element in ‘arr1’, we will iterate through all its corresponding elements in ‘arr2’ and update ‘dp’ accordingly.

Algorithm:

• Declare a hashmap, say ‘oneToMany’ to do a one-to-many mapping between each element in ‘arr1’ to its corresponding element in ‘arr2’.
• Run a loop for ‘i’ from ‘0’ to ‘M’ - 1
  • Insert ‘i’ into ‘oneToMany[arr2[i]]’.
• Declare an array of integers, say ‘dp’ of size ‘M’, where ‘dp[i]’ will denote the length of the longest common subsequence between ‘arr1’ and ‘arr2[0 . . . i ]’ and ending at ‘i’, and initialize it with 0.
• Build a Segment Tree for ‘dp’ to find the maximum element in a subarray efficiently.
• Run a loop for ‘i’ from 0 to ‘N’ - 1
  • Run a loop for ‘j’ from size of ‘oneToMany[arr1[i]]’ - 1 to 0.
    • Declare an integer, say ‘pos’ to store the position of the current element, and initialize it with ‘oneToMany[i][j]’.
    • Find the maximum element in ‘dp[0 . . . pos]’ using Segment Tree and store its value in a variable ‘prevValue’.
    • Update ‘dp[pos]’ as ‘dp[pos]’ = prevValue + 1, since we are extending our common subsequence till ‘pos’.
    • Update the value of ‘dp[pos]’ in the segment tree.
• Declare an integer, say ‘lengthLCS’, to store the length of the longest common subsequence between ‘arr1’ and 'arr2' and initialize it with 0.
• Run a loop for ‘i’ from 0 to ‘M’ - 1
  • Update ‘lengthLCS’ as the maximum of ‘lengthLCS’ and ‘dp[i]’.
• Return (‘N’ - ‘lengthLCS’), as this is the minimum number of elements that we need to insert in ‘arr2’ to make ‘arr1’ a subsequence.