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’.

O(2 ^ (N + M)), where ‘N’ and ‘M’ denote the number elements in ‘arr1’ and ‘arr2’, respectively.

In the worst case, we have to insert all the elements of ‘arr1’ into the ‘arr2’ array. After insertion, the size of ‘arr2’ will be ‘N’ + ‘M’. For any i-th position in ‘arr2’, we have two choices, either we will insert an element at the i-th position, or we will not insert.

Therefore, we have a total of 2 ^ (N + M) different ways to insert elements of ‘arr1’ into the ‘arr2’ array, and for each insertion, we take O(1) time. Hence, the total time complexity will be O(2 ^ (N + M)).

O(N + M), where ‘N’ and ‘M’ denote the number elements in ‘arr1’ and ‘arr2’, respectively.

Our ‘allInsertions’ function requires O(N + M) space in the form of recursive stack space.

Therefore, the total space complexity will be O(N + M).