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 * 2M)
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 Bint 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 approachimport 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 Bdef 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 Codeif __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 approachusing 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 Bstatic 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 Codepublic 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 Bfunction 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 arraysvar A = [1, 2, 3, 4, 5];var B = [2, 5, 6, 4, 9, 12];var M = A.length;var N = B.length;// Function Calldocument.write( minElements(A, B, M, N));</script> |
Output:
3
Time Complexity: O(N logN)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
