Minimize elements to be added to a given array such that it contains another given array as its subsequence | Set 2

0 0 7 minutes read

Given an array A[] consisting of N distinct integers and another array B[] consisting of M integers, the task is to find the minimum number of elements to be added to the array B[] such that the array A[] becomes the subsequence of the array B[].

Examples:

Input: N = 5, M = 6, A[] = {1, 2, 3, 4, 5}, B[] = {2, 5, 6, 4, 9, 12}
Output: 3
Explanation:
Below are the elements that need to be added:
1) Add 1 before element 2 of B[]
2) Add 3 after element 6 of B[]
3) Add 5 in the last position of B[].
Therefore, the resulting array B[] is {1, 2, 5, 6, 3, 4, 9, 12, 5}.
Hence, A[] is the subsequence of B[] after adding 3 elements.

Input: N = 5, M = 5, A[] = {3, 4, 5, 2, 7}, B[] = {3, 4, 7, 9, 2}
Output: 2
Explanation:
Below are the elements that need to be added:
1) Add 5 after element 4.
2) Add 2 after element 5.
Therefore, the resulting array B[] is {3, 4, 5, 2, 7, 9, 2}.
Hence, 2 elements are required to be added.

Naive Approach: Refer to the previous post of this article for the simplest approach to solve the problem.

Time Complexity: O(N * 2^M)
Auxiliary Space: O(M + N)

Dynamic Programming Approach: Refer to the previous post of this article for the Longest Common Subsequence based approach.

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

Efficient Approach: The idea is similar to finding the Longest Increasing Subsequence(LIS) from the array B[]. Follow the steps below to solve the problem:

Consider elements of array B[] which are present in the array A[], and store the indices of each element of the array A[] in a Map
Then, find the LIS array subseq[] using Binary Search which consists of the indices in increasing order.
Finally, the minimum number of elements to be inserted into array B[] is equal to N – len(LIS), where len(LIS) is calculated using Binary Search in the above steps.

Below is the implementation of the above approach:

C++

// C++ program for the 
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return minimum 
// element to be added in array 
// B so that array A become 
// subsequence of array B
int minElements(int A[], int B[], 
                int N, int M)
{
  // Stores indices of the
  // array elements
  map<int, int> map;
 
  // Iterate over the array
  for (int i = 0; i < N; i++) 
  {
    // Store the indices of
    // the array elements
    map[A[i]] = i;
  }
 
  // Stores the LIS
  vector<int> subseq;
 
  int l = 0, r = -1;
 
  for (int i = 0; i < M; i++) 
  {
    // Check if element B[i]
    // is in array A[]
    if (map.find(B[i]) != 
        map.end()) 
    {
      int e = map[B[i]];
 
      // Perform Binary Search
      while (l <= r) 
      {
        // Find the value of
        // mid m
        int m = l + (r - l) / 2;
 
        // Update l and r
        if (subseq[m] < e)
          l = m + 1;
        else
          r = m - 1;
      }
 
      // If found better element
      // 'e' for pos r + 1
      if (r + 1 < subseq.size()) 
      {
        subseq[r + 1] = e;
      }
 
      // Otherwise, extend the
      // current subsequence
      else
      {
        subseq.push_back(e);
      }
 
      l = 0;
      r = subseq.size() - 1;
    }
  }
 
  // Return the answer
  return N - subseq.size();
}
 
// Driver code 
int main()
{
  // Given arrays
  int A[] = {1, 2, 3, 4, 5};
  int B[] = {2, 5, 6, 4, 9, 12};
 
  int M = sizeof(A) / 
          sizeof(A[0]);
  int N = sizeof(B) /
          sizeof(B[0]);
 
  // Function Call
  cout << minElements(A, B, 
                      M, N);
 
  return 0;
}
 
// This code is contributed by divyeshrabadiya07

Java

// Java program for the above approach
 
import java.util.*;
import java.lang.*;
 
class GFG {
 
    // Function to return minimum element
    // to be added in array B so that array
    // A become subsequence of array B
    static int minElements(
        int[] A, int[] B, int N, int M)
    {
 
        // Stores indices of the
        // array elements
        Map<Integer, Integer> map
            = new HashMap<>();
 
        // Iterate over the array
        for (int i = 0;
             i < A.length; i++) {
 
            // Store the indices of
            // the array elements
            map.put(A[i], i);
        }
 
        // Stores the LIS
        ArrayList<Integer> subseq
            = new ArrayList<>();
 
        int l = 0, r = -1;
 
        for (int i = 0; i < M; i++) {
 
            // Check if element B[i]
            // is in array A[]
            if (map.containsKey(B[i])) {
 
                int e = map.get(B[i]);
 
                // Perform Binary Search
                while (l <= r) {
 
                    // Find the value of
                    // mid m
                    int m = l + (r - l) / 2;
 
                    // Update l and r
                    if (subseq.get(m) < e)
                        l = m + 1;
                    else
                        r = m - 1;
                }
 
                // If found better element
                // 'e' for pos r + 1
                if (r + 1 < subseq.size()) {
                    subseq.set(r + 1, e);
                }
 
                // Otherwise, extend the
                // current subsequence
                else {
                    subseq.add(e);
                }
 
                l = 0;
                r = subseq.size() - 1;
            }
        }
 
        // Return the answer
        return N - subseq.size();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given arrays
        int[] A = { 1, 2, 3, 4, 5 };
        int[] B = { 2, 5, 6, 4, 9, 12 };
 
        int M = A.length;
        int N = B.length;
 
        // Function Call
        System.out.println(
            minElements(A, B, M, N));
    }
}

Python3

# Python3 program for the above approach
 
# Function to return minimum element
# to be added in array B so that array
# A become subsequence of array B
def minElements(A, B, N, M):
     
    # Stores indices of the
    # array elements
    map = {}
 
    # Iterate over the array
    for i in range(len(A)):
 
        # Store the indices of
        # the array elements
        map[A[i]] = i
  
    # Stores the LIS
    subseq = []
 
    l = 0
    r = -1
 
    for i in range(M):
 
        # Check if element B[i]
        # is in array A[]
        if B[i] in map:
            e = map[B[i]]
 
            # Perform Binary Search
            while (l <= r):
 
                # Find the value of
                # mid m
                m = l + (r - l) // 2
 
                # Update l and r
                if (subseq[m] < e):
                    l = m + 1
                else:
                    r = m - 1
 
            # If found better element
            # 'e' for pos r + 1
            if (r + 1 < len(subseq)):
                subseq[r + 1]= e
 
            # Otherwise, extend the
            # current subsequence
            else:
                subseq.append(e)
 
            l = 0
            r = len(subseq) - 1
 
    # Return the answer
    return N - len(subseq)
 
# Driver Code
if __name__ == '__main__':
     
    # Given arrays
    A = [ 1, 2, 3, 4, 5 ]
    B = [ 2, 5, 6, 4, 9, 12 ]
 
    M = len(A)
    N = len(B)
 
    # Function call
    print(minElements(A, B, M, N))
 
# This code is contributed by mohit kumar 29

C#

// C# program for 
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to return minimum element
// to be added in array B so that array
// A become subsequence of array B
static int minElements(int[] A, int[] B, 
                       int N, int M)
{
  // Stores indices of the
  // array elements
  Dictionary<int, 
             int> map = new Dictionary<int, 
                                       int>();
   
  // Iterate over the array
  for (int i = 0;
           i < A.Length; i++) 
  {
    // Store the indices of
    // the array elements
    map.Add(A[i], i);
  }
 
  // Stores the LIS
  List<int> subseq = new List<int>();
 
  int l = 0, r = -1;
 
  for (int i = 0; i < M; i++) 
  {
    // Check if element B[i]
    // is in array []A
    if (map.ContainsKey(B[i])) 
    {
      int e = map[B[i]];
 
      // Perform Binary Search
      while (l <= r) 
      {
        // Find the value of
        // mid m
        int m = l + (r - l) / 2;
 
        // Update l and r
        if (subseq[m] < e)
          l = m + 1;
        else
          r = m - 1;
      }
 
      // If found better element
      // 'e' for pos r + 1
      if (r + 1 < subseq.Count) 
      {
        subseq[r + 1] = e;
      }
 
      // Otherwise, extend the
      // current subsequence
      else
      {
        subseq.Add(e);
      }
 
      l = 0;
      r = subseq.Count - 1;
    }
  }
 
  // Return the answer
  return N - subseq.Count;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given arrays
  int[] A = {1, 2, 3, 4, 5};
  int[] B = {2, 5, 6, 4, 9, 12};
 
  int M = A.Length;
  int N = B.Length;
 
  // Function Call
  Console.WriteLine(minElements(A, B, 
                                M, N));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
// Javascript program for the 
// above approach
 
// Function to return minimum 
// element to be added in array 
// B so that array A become 
// subsequence of array B
function minElements(A, B, N, M)
{
  // Stores indices of the
  // array elements
  var map = new Map();
 
  // Iterate over the array
  for (var i = 0; i < N; i++) 
  {
    // Store the indices of
    // the array elements
    map.set(A[i], i);
  }
 
  // Stores the LIS
  var subseq = [];
 
  var l = 0, r = -1;
 
  for (var i = 0; i < M; i++) 
  {
    // Check if element B[i]
    // is in array A[]
    if (map.has(B[i])) 
    {
      var e = map.get(B[i]);
 
      // Perform Binary Search
      while (l <= r) 
      {
        // Find the value of
        // mid m
        var m = l + parseInt((r - l) / 2);
 
        // Update l and r
        if (subseq[m] < e)
          l = m + 1;
        else
          r = m - 1;
      }
 
      // If found better element
      // 'e' for pos r + 1
      if (r + 1 < subseq.length) 
      {
        subseq[r + 1] = e;
      }
 
      // Otherwise, extend the
      // current subsequence
      else
      {
        subseq.push(e);
      }
 
      l = 0;
      r = subseq.length - 1;
    }
  }
 
  // Return the answer
  return N - subseq.length;
}
 
// Driver code 
// Given arrays
var A = [1, 2, 3, 4, 5];
var B = [2, 5, 6, 4, 9, 12];
var M = A.length;
var N = B.length;
// Function Call
document.write( minElements(A, B, 
                    M, N));
 
</script>

Output:

Time Complexity: O(N logN)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!