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

0 0 12 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 element that are needed 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 are needed 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: The naive approach is to generate all the subsequences of the array B and then find that subsequence such that on adding a minimum number of elements from the array A to make it equal to the array A. Print the minimum count of element added.
Time Complexity: O(N*2^M)
Auxiliary Space: O(M+N)

Efficient Approach: The above approach can be optimized using Dynamic Programming. The idea is to find the Longest Common Subsequence between the given two arrays A and B. The main observation is that the minimum number of elements to be added in B[] such that A[] becomes its subsequence can be found by subtracting the length of the longest common subsequence from the length of the array A[].

Therefore, the difference between the length of the array A[] and length of the Longest Common Subsequence is the required result.

Below is the implementation of the above approach:

C++14

// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that finds the minimum number
// of the element must be added to make A
// as a subsequence in B
int transformSubsequence(int n, int m,
                         vector<int> A,
                         vector<int> B)
{
     
    // Base Case
    if (B.size() == 0)
        return n;
 
    // dp[i][j] indicates the length of
    // LCS of A of length i & B of length j
    vector<vector<int>> dp(n + 1, 
           vector<int>(m + 1, 0));
 
    for(int i = 0; i < n + 1; i++)
    {
        for(int j = 0; j < m + 1; j++)
        {
             
            // If there are no elements
            // either in A or B then the
            // length of lcs is 0
            if (i == 0 or j == 0)
                dp[i][j] = 0;
 
            // If the element present at
            // ith and jth index of A and B
            // are equal then include in LCS
            else if (A[i - 1] == B[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
 
            // If they are not equal then
            // take the max
            else
                dp[i][j] = max(dp[i - 1][j],
                               dp[i][j - 1]);
        }
    }
 
    // Return difference of length
    // of A and lcs of A and B
    return n - dp[n][m];
}
 
// Driver Code
int main()
{
    int N = 5;
    int M = 6;
 
    // Given sequence A and B
    vector<int> A = { 1, 2, 3, 4, 5 };
    vector<int> B = { 2, 5, 6, 4, 9, 12 };
 
    // Function call
    cout << transformSubsequence(N, M, A, B);
 
    return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java program for 
// the above approach
import java.util.*;
class GFG{
 
// Function that finds the minimum number
// of the element must be added to make A
// as a subsequence in B
static int transformSubsequence(int n, int m,
                                int []A, int []B)
{
  // Base Case
  if (B.length == 0)
    return n;
 
  // dp[i][j] indicates the length of
  // LCS of A of length i & B of length j
  int [][]dp = new int[n + 1][m + 1];
 
  for(int i = 0; i < n + 1; i++)
  {
    for(int j = 0; j < m + 1; j++)
    {
      // If there are no elements
      // either in A or B then the
      // length of lcs is 0
      if (i == 0 || j == 0)
        dp[i][j] = 0;
 
      // If the element present at
      // ith and jth index of A and B
      // are equal then include in LCS
      else if (A[i - 1] == B[j - 1])
        dp[i][j] = 1 + dp[i - 1][j - 1];
 
      // If they are not equal then
      // take the max
      else
        dp[i][j] = Math.max(dp[i - 1][j],
                            dp[i][j - 1]);
    }
  }
 
  // Return difference of length
  // of A and lcs of A and B
  return n - dp[n][m];
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 5;
  int M = 6;
 
  // Given sequence A and B
  int []A = {1, 2, 3, 4, 5};
  int []B = {2, 5, 6, 4, 9, 12};
 
  // Function call
  System.out.print(transformSubsequence(N, M, A, B));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
 
# Function that finds the minimum number
# of the element must be added to make A
# as a subsequence in B
def transformSubsequence(n, m, A, B):
 
    # Base Case
    if B is None or len(B) == 0:
        return n
 
    # dp[i][j] indicates the length of
    # LCS of A of length i & B of length j
    dp = [[0 for col in range(m + 1)]
        for row in range(n + 1)]
 
    for i in range(n + 1):
 
        for j in range(m + 1):
 
            # If there are no elements
            # either in A or B then the
            # length of lcs is 0
            if i == 0 or j == 0:
                dp[i][j] = 0
 
            # If the element present at
            # ith and jth index of A and B
            # are equal then include in LCS
            elif A[i-1] == B[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
 
            # If they are not equal then
            # take the max
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
 
    # Return difference of length
    # of A and lcs of A and B
    return n - dp[n][m]
 
 
# Driver Code
if __name__ == "__main__":
 
    N = 5
    M = 6
     
    # Given Sequence A and B
    A = [1, 2, 3, 4, 5]
    B = [2, 5, 6, 4, 9, 12]
 
    # Function Call
    print(transformSubsequence(N, M, A, B))

C#

// C# program for 
// the above approach
using System;
class GFG{
 
// Function that finds the minimum number
// of the element must be added to make A
// as a subsequence in B
static int transformSubsequence(int n, int m,
                                int []A, int []B)
{
  // Base Case
  if (B.Length == 0)
    return n;
 
  // dp[i,j] indicates the length of
  // LCS of A of length i & B of length j
  int [,]dp = new int[n + 1, m + 1];
 
  for(int i = 0; i < n + 1; i++)
  {
    for(int j = 0; j < m + 1; j++)
    {
      // If there are no elements
      // either in A or B then the
      // length of lcs is 0
      if (i == 0 || j == 0)
        dp[i, j] = 0;
 
      // If the element present at
      // ith and jth index of A and B
      // are equal then include in LCS
      else if (A[i - 1] == B[j - 1])
        dp[i, j] = 1 + dp[i - 1, j - 1];
 
      // If they are not equal then
      // take the max
      else
        dp[i, j] = Math.Max(dp[i - 1, j],
                            dp[i, j - 1]);
    }
  }
 
  // Return difference of length
  // of A and lcs of A and B
  return n - dp[n, m];
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 5;
  int M = 6;
 
  // Given sequence A and B
  int []A = {1, 2, 3, 4, 5};
  int []B = {2, 5, 6, 4, 9, 12};
 
  // Function call
  Console.Write(transformSubsequence(N, M, 
                                     A, B));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function that finds the minimum number
// of the element must be added to make A
// as a subsequence in B
function transformSubsequence(n, m, A, B)
{
     
    // Base Case
    if (B.length == 0)
        return n;
 
    // dp[i][j] indicates the length of
    // LCS of A of length i & B of length j
    var dp = Array.from(Array(n+1), ()=>Array(m+1).fill(0));
 
    for(var i = 0; i < n + 1; i++)
    {
        for(var j = 0; j < m + 1; j++)
        {
             
            // If there are no elements
            // either in A or B then the
            // length of lcs is 0
            if (i == 0 || j == 0)
                dp[i][j] = 0;
 
            // If the element present at
            // ith and jth index of A and B
            // are equal then include in LCS
            else if (A[i - 1] == B[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
 
            // If they are not equal then
            // take the max
            else
                dp[i][j] = Math.max(dp[i - 1][j],
                               dp[i][j - 1]);
        }
    }
 
    // Return difference of length
    // of A and lcs of A and B
    return n - dp[n][m];
}
 
// Driver Code
 
var N = 5;
var M = 6;
 
// Given sequence A and B
var A = [1, 2, 3, 4, 5 ];
var B = [2, 5, 6, 4, 9, 12 ];
 
// Function call
document.write( transformSubsequence(N, M, A, B));
 
 
 
</script>

Output:

Time Complexity: O(M*M), where N and M are the lengths of array A[] and B[] respectively.
Auxiliary Space: O(M*N)

Efficient approach : Space optimization

In previous approach the dp[i][j] is depend upon the current and previous row of 2D matrix. So to optimize space we use a 1D vectors dp to store previous value and use prev to store the previous diagonal element and get the current computation.

Implementation Steps:

Define a vector dp of size m+1 and initialize its first element to 0.
For each element j in B, iterate in reverse order from n to 1 and update dp[i] as follows:
a. If A[i-1] == B[j-1], set dp[i] to the previous value of dp[i-1] (diagonal element).
b. If A[i-1] != B[j-1], set dp[i] to the maximum value between dp[i] and dp[i-1]+1 (value on the left).
Finally, return n – dp[m].

Implementation:

C++

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that finds the minimum number
// of the element must be added to make A
// as a subsequence in B
int transformSubsequence(int n, int m,
                          vector<int> A,
                          vector<int> B)
{
 
    // Base Case
    if (B.size() == 0)
        return n;
 
    // dp[j] indicates the length of
    // LCS of A and B of length j
    vector<int> dp(m + 1, 0);
 
    for(int i = 1; i < n + 1; i++)
    {
        int prev = dp[0];
        for(int j = 1; j < m + 1; j++)
        {
 
            // If the element present at
            // ith and jth index of A and B
            // are equal then include in LCS
            int curr = dp[j];
            if (A[i - 1] == B[j - 1])
                dp[j] = 1 + prev;
 
            // If they are not equal then
            // take the max
            else
                dp[j] = max(dp[j], dp[j - 1]);
 
            prev = curr;
        }
    }
 
    // Return difference of length
    // of A and lcs of A and B
    return n - dp[m];
}
 
// Driver Code
int main()
{
    int N = 5;
    int M = 6;
 
    // Given sequence A and B
    vector<int> A = { 1, 2, 3, 4, 5 };
    vector<int> B = { 2, 5, 6, 4, 9, 12 };
 
    // Function call
    cout << transformSubsequence(N, M, A, B);
 
    return 0;
}
// this code is contributed by bhardwajji

Java

import java.util.*;
 
public class MinimumAdditions {
 
    // Function that finds the minimum number
    // of the element must be added to make A
    // as a subsequence in B
    public static int transformSubsequence(int n, int m,
                          List<Integer> A,
                          List<Integer> B)
    {
 
        // Base Case
        if (B.size() == 0)
            return n;
 
        // dp[j] indicates the length of
        // LCS of A and B of length j
        int[] dp = new int[m + 1];
 
        for(int i = 1; i < n + 1; i++)
        {
            int prev = dp[0];
            for(int j = 1; j < m + 1; j++)
            {
 
                // If the element present at
                // ith and jth index of A and B
                // are equal then include in LCS
                int curr = dp[j];
                if (A.get(i - 1).equals(B.get(j - 1)))
                    dp[j] = 1 + prev;
 
                // If they are not equal then
                // take the max
                else
                    dp[j] = Math.max(dp[j], dp[j - 1]);
 
                prev = curr;
            }
        }
 
        // Return difference of length
        // of A and lcs of A and B
        return n - dp[m];
    }
 
    // Driver Code
    public static void main(String[] args) {
        int N = 5;
        int M = 6;
 
        // Given sequence A and B
        List<Integer> A = Arrays.asList(1, 2, 3, 4, 5);
        List<Integer> B = Arrays.asList(2, 5, 6, 4, 9, 12);
 
        // Function call
        System.out.println(transformSubsequence(N, M, A, B));
    }
}

Python3

# Python program for above approach
 
# Function that finds the minimum number
# of the element must be added to make A
# as a subsequence in B
def transformSubsequence(n, m, A, B):
 
    # Base Case
    if len(B) == 0:
        return n
 
    # dp[j] indicates the length of
    # LCS of A and B of length j
    dp = [0] * (m + 1)
 
    for i in range(1, n + 1):
        prev = dp[0]
        for j in range(1, m + 1):
 
            # If the element present at
            # ith and jth index of A and B
            # are equal then include in LCS
            curr = dp[j]
            if A[i - 1] == B[j - 1]:
                dp[j] = 1 + prev
 
            # If they are not equal then
            # take the max
            else:
                dp[j] = max(dp[j], dp[j - 1])
 
            prev = curr
 
    # Return difference of length
    # of A and lcs of A and B
    return n - dp[m]
 
# Driver Code
if __name__ == '__main__':
    N = 5
    M = 6
 
    # Given sequence A and B
    A = [1, 2, 3, 4, 5]
    B = [2, 5, 6, 4, 9, 12]
 
    # Function call
    print(transformSubsequence(N, M, A, B))

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
    static int TransformSubsequence(int n, int m, List<int> A, List<int> B)
    {
        // Base Case
        if (B.Count == 0)
            return n;
 
        // dp[j] indicates the length of
        // LCS of A and B of length j
        var dp = new int[m + 1];
 
        for (int i = 1; i < n + 1; i++)
        {
            int prev = dp[0];
            for (int j = 1; j < m + 1; j++)
            {
                // If the element present at
                // ith and jth index of A and B
                // are equal then include in LCS
                int curr = dp[j];
                if (A[i - 1] == B[j - 1])
                    dp[j] = 1 + prev;
 
                // If they are not equal then
                // take the max
                else
                    dp[j] = Math.Max(dp[j], dp[j - 1]);
 
                prev = curr;
            }
        }
 
        // Return difference of length
        // of A and lcs of A and B
        return n - dp[m];
    }
 
    static void Main(string[] args)
    {
        int N = 5;
        int M = 6;
 
        // Given sequence A and B
        var A = new List<int> { 1, 2, 3, 4, 5 };
        var B = new List<int> { 2, 5, 6, 4, 9, 12 };
 
        // Function call
        Console.WriteLine(TransformSubsequence(N, M, A, B));
    }
}

Javascript

// Define a function that finds the minimum number
// of the element must be added to make A as a subsequence in B
function transformSubsequence(n, m, A, B) {
    // Base Case: if B is an empty list, then all elements of A 
    // need to be added to B to make A a subsequence of B
if (B.length === 0)
    return n;
 
// Define a dynamic programming array dp of length m+1 
// where dp[j] indicates the length of the longest common subsequence (LCS) 
// of A and B of length j
let dp = new Array(m + 1).fill(0);
 
// Loop through the elements of A
for(let i = 1; i < n + 1; i++) {
    // Define a variable prev to keep track of the value of dp[j-1] 
    // in the previous iteration
    let prev = dp[0];
    // Loop through the elements of B
    for(let j = 1; j < m + 1; j++) {
        // Define a variable curr to keep track of the value of dp[j] 
        // in the previous iteration
        let curr = dp[j];
        // If the ith element of A is equal to the jth element of B, 
        // include this element in the LCS
        if (A[i - 1] === B[j - 1])
            dp[j] = 1 + prev;
        // If the ith element of A is not equal to the jth element of B, 
        // then take the maximum of dp[j] and dp[j-1] to find the 
        // longest common subsequence so far
        else
            dp[j] = Math.max(dp[j], dp[j - 1]);
        // Update prev with the value of curr for the next iteration
        prev = curr;
    }
}
 
// Return the difference of the length of A and the LCS of A and B, which is the minimum number of elements that must be added to B to make A a subsequence of B
return n - dp[m];
}
 
// Test the function with the given input
let N = 5;
let M = 6;
 
let A = [1, 2, 3, 4, 5];
let B = [2, 5, 6, 4, 9, 12];
 
console.log(transformSubsequence(N, M, A, B));

Output

Time Complexity: O(M*M), where N and M are the lengths of array A[] and B[] respectively.
Auxiliary Space: O(M)

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!