Longest subarray of an array which is a subsequence in another array

0 0 9 minutes read

Given two arrays arr1[] and arr2[], the task is to find the longest subarray of arr1[] which is a subsequence of arr2[].

Examples:

Input: arr1[] = {4, 2, 3, 1, 5, 6}, arr2[] = {3, 1, 4, 6, 5, 2}
Output: 3
Explanation: The longest subarray of arr1[] which is a subsequence in arr2[] is {3, 1, 5}

Input: arr1[] = {3, 2, 4, 7, 1, 5, 6, 8, 10, 9}, arr2[] = {9, 2, 4, 3, 1, 5, 6, 8, 10, 7}
Output: 5
Explanation: The longest subarray in arr1[] which is a subsequence in arr2[] is {1, 5, 6, 8, 10}.

Approach: The idea is to use Dynamic Programming to solve this problem. Follow the steps below to solve the problem:

Initialize a DP[][] table, where DP[i][j] stores the length of the longest subarray up to the i^th index in arr1[] which is a subsequence in arr2[] up to the j^th index.
Now, traverse over both the arrays and perform the following:
- Case 1: If arr1[i] and arr2[j] are equal, add 1 to DP[i – 1][j – 1] as arr1[i] and arr2[j] contribute to the required length of the longest subarray.
- Case 2: If arr1[i] and arr2[j] are not equal, set DP[i][j] = DP[i – 1][j].
Finally, print the maximum value present in DP[][] table as the required answer.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
    // Function to find the length of the
    // longest subarray in arr1[] which
    // is a subsequence in arr2[]
    int LongSubarrSeq(int arr1[], int arr2[], int M, int N)
    {
        // Length of the array arr1[]
 
        // Length of the required
        // longest subarray
        int maxL = 0;
 
        // Initialize DP[]array
        int DP[M + 1][N + 1];
 
        // Traverse array arr1[]
        for (int i = 1; i <= M; i++)
        {
 
            // Traverse array arr2[]
            for (int j = 1; j <= N; j++)
            {
                if (arr1[i - 1] == arr2[j - 1])
                {
 
                    // arr1[i - 1] contributes to
                    // the length of the subarray
                    DP[i][j] = 1 + DP[i - 1][j - 1];
                }
 
                // Otherwise
                else
                {
 
                    DP[i][j] = DP[i][j - 1];
                }
            }
        }
 
        // Find the maximum value
        // present in DP[][]
        for (int i = 1; i <= M; i++) 
        {
            for (int j = 1; j <= N; j++)
            {
                maxL = max(maxL, DP[i][j]);
            }
        }
 
        // Return the result
        return maxL;
    }
 
 
// Driver Code
int main()
{
    int arr1[] = { 4, 2, 3, 1, 5, 6 };
    int M = sizeof(arr1) / sizeof(arr1[0]);
     
    int arr2[] = { 3, 1, 4, 6, 5, 2 };
    int N = sizeof(arr2) / sizeof(arr2[0]);
 
    // Function call to find the length
    // of the longest required subarray
    cout << LongSubarrSeq(arr1, arr2, M, N) <<endl;
    return 0;
}
 
// This code is contributed by code_hunt.

Java

// Java program
// for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to find the length of the
    // longest subarray in arr1[] which
    // is a subsequence in arr2[]
    private static int LongSubarrSeq(
        int[] arr1, int[] arr2)
    {
        // Length of the array arr1[]
        int M = arr1.length;
 
        // Length of the array arr2[]
        int N = arr2.length;
 
        // Length of the required
        // longest subarray
        int maxL = 0;
 
        // Initialize DP[]array
        int[][] DP = new int[M + 1][N + 1];
 
        // Traverse array arr1[]
        for (int i = 1; i <= M; i++) {
 
            // Traverse array arr2[]
            for (int j = 1; j <= N; j++) {
 
                if (arr1[i - 1] == arr2[j - 1]) {
 
                    // arr1[i - 1] contributes to
                    // the length of the subarray
                    DP[i][j] = 1 + DP[i - 1][j - 1];
                }
 
                // Otherwise
                else {
 
                    DP[i][j] = DP[i][j - 1];
                }
            }
        }
 
        // Find the maximum value
        // present in DP[][]
        for (int i = 1; i <= M; i++) {
 
            for (int j = 1; j <= N; j++) {
 
                maxL = Math.max(maxL, DP[i][j]);
            }
        }
 
        // Return the result
        return maxL;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr1 = { 4, 2, 3, 1, 5, 6 };
        int[] arr2 = { 3, 1, 4, 6, 5, 2 };
 
        // Function call to find the length
        // of the longest required subarray
        System.out.println(LongSubarrSeq(arr1, arr2));
    }
}

Python3

# Python program
# for the above approach
 
# Function to find the length of the
# longest subarray in arr1 which
# is a subsequence in arr2
def LongSubarrSeq(arr1, arr2):
   
    # Length of the array arr1
    M = len(arr1);
 
    # Length of the array arr2
    N = len(arr2);
 
    # Length of the required
    # longest subarray
    maxL = 0;
 
    # Initialize DParray
    DP = [[0 for i in range(N + 1)] for j in range(M + 1)];
 
    # Traverse array arr1
    for i in range(1, M + 1):
 
        # Traverse array arr2
        for j in range(1, N + 1):
            if (arr1[i - 1] == arr2[j - 1]):
 
                # arr1[i - 1] contributes to
                # the length of the subarray
                DP[i][j] = 1 + DP[i - 1][j - 1];
 
            # Otherwise
            else:
 
                DP[i][j] = DP[i][j - 1];
 
    # Find the maximum value
    # present in DP
    for i in range(M + 1):
 
        # Traverse array arr2
        for j in range(1, N + 1):
            maxL = max(maxL, DP[i][j]);
 
    # Return the result
    return maxL;
 
# Driver Code
if __name__ == '__main__':
    arr1 = [4, 2, 3, 1, 5, 6];
    arr2 = [3, 1, 4, 6, 5, 2];
 
    # Function call to find the length
    # of the longest required subarray
    print(LongSubarrSeq(arr1, arr2));
 
    # This code contributed by shikhasingrajput

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the length of the
// longest subarray in arr1[] which
// is a subsequence in arr2[]
private static int LongSubarrSeq(int[] arr1, 
                                 int[] arr2)
{
     
    // Length of the array arr1[]
    int M = arr1.Length;
     
    // Length of the array arr2[]
    int N = arr2.Length;
     
    // Length of the required
    // longest subarray
    int maxL = 0;
     
    // Initialize DP[]array
    int[,] DP = new int[M + 1, N + 1];
 
    // Traverse array arr1[]
    for(int i = 1; i <= M; i++) 
    {
         
        // Traverse array arr2[]
        for(int j = 1; j <= N; j++) 
        {
            if (arr1[i - 1] == arr2[j - 1])
            {
                 
                // arr1[i - 1] contributes to
                // the length of the subarray
                DP[i, j] = 1 + DP[i - 1, j - 1];
            }
 
            // Otherwise
            else
            {
                DP[i, j] = DP[i, j - 1];
            }
        }
    }
 
    // Find the maximum value
    // present in DP[][]
    for(int i = 1; i <= M; i++) 
    {
        for(int j = 1; j <= N; j++) 
        {
            maxL = Math.Max(maxL, DP[i, j]);
        }
    }
     
    // Return the result
    return maxL;
}
 
// Driver Code
static public void Main()
{
    int[] arr1 = { 4, 2, 3, 1, 5, 6 };
    int[] arr2 = { 3, 1, 4, 6, 5, 2 };
     
    // Function call to find the length
    // of the longest required subarray
    Console.WriteLine(LongSubarrSeq(arr1, arr2));
}
}
 
// This code is contributed by susmitakundugoaldanga

Javascript

<script>
// javascript program of the above approach
 
    // Function to find the length of the
    // longest subarray in arr1[] which
    // is a subsequence in arr2[]
    function LongSubarrSeq(
        arr1, arr2)
    {
        // Length of the array arr1[]
        let M = arr1.length;
 
        // Length of the array arr2[]
        let N = arr2.length;
 
        // Length of the required
        // longest subarray
        let maxL = 0;
 
        // Initialize DP[]array
        let DP = new Array(M + 1);
         
        // Loop to create 2D array using 1D array
        for (var i = 0; i < DP.length; i++) {
            DP[i] = new Array(2);
        }
         
        for (var i = 0; i < DP.length; i++) {
            for (var j = 0; j < DP.length; j++) {
            DP[i][j] = 0;
        }
        }
 
        // Traverse array arr1[]
        for (let i = 1; i <= M; i++) {
 
            // Traverse array arr2[]
            for (let j = 1; j <= N; j++) {
 
                if (arr1[i - 1] == arr2[j - 1]) {
 
                    // arr1[i - 1] contributes to
                    // the length of the subarray
                    DP[i][j] = 1 + DP[i - 1][j - 1];
                }
 
                // Otherwise
                else {
 
                    DP[i][j] = DP[i][j - 1];
                }
            }
        }
 
        // Find the maximum value
        // present in DP[][]
        for (let i = 1; i <= M; i++) {
 
            for (let j = 1; j <= N; j++) {
 
                maxL = Math.max(maxL, DP[i][j]);
            }
        }
 
        // Return the result
        return maxL;
    }
 
    // Driver Code
     
        let arr1 = [ 4, 2, 3, 1, 5, 6 ];
        let arr2 = [ 3, 1, 4, 6, 5, 2 ];
 
        // Function call to find the length
        // of the longest required subarray
        document.write(LongSubarrSeq(arr1, arr2));
 
</script>

Output

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

Efficient Approach: Space optimization: In the previous approach the current value dp[i][j] only depends upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.

Implementation steps:

Create a 1D vector dp of size n+1.
Initialize a variable maxi to store the final answer and update it by iterating through the Dp.
Set a base case by initializing the values of DP.
Now iterate over subproblems with the help of a nested loop and get the current value from previous computations.
Now Create variables prev, temp used to store the previous values from previous computations.
After every iteration assign the value of temp to temp for further iteration.
At last return and print the final answer stored in maxi.

Implementation:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of the
// longest subarray in arr1[]
// which is a subsequence in arr2[]
int LongSubarrSeq(int arr1[], int arr2[], int M, int N)
{
 
    // to store final result
    int maxL = 0;
 
    // to store previous computations
    // Initialize DP[] vector
    vector<int> DP(N + 1, 0);
 
    // iterate over subproblems to get the
    // current value from previous computations
    for (int i = 1; i <= M; i++) {
        int prev = 0;
        for (int j = 1; j <= N; j++) {
            // Store current DP[j] value
            int temp = DP[j];
            if (arr1[i - 1] == arr2[j - 1]) {
                DP[j] = 1 + prev;
                maxL = max(maxL, DP[j]);
            }
            else {
                DP[j] = DP[j - 1];
            }
 
            // Update previous DP[j] value
            prev = temp;
        }
    }
 
    // Return final answer
    return maxL;
}
 
// Driver Code
int main()
{
    int arr1[] = { 4, 2, 3, 1, 5, 6 };
    int M = sizeof(arr1) / sizeof(arr1[0]);
 
    int arr2[] = { 3, 1, 4, 6, 5, 2 };
    int N = sizeof(arr2) / sizeof(arr2[0]);
 
    cout << LongSubarrSeq(arr1, arr2, M, N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
public class Main {
  // Function to find the length of the
// longest subarray in arr1[]
// which is a subsequence in arr2[]
static int LongSubarrSeq(int arr1[], int arr2[], int M, int N)
{
 
    // to store final result
    int maxL = 0;
 
    // to store previous computations
    // Initialize DP[] vector
    int DP[] = new int[N + 1];
 
    Arrays.fill(DP, 0);
 
    // iterate over subproblems to get the
    // current value from previous computations
    for (int i = 1; i <= M; i++) {
        int prev = 0;
        for (int j = 1; j <= N; j++) {
            // Store current DP[j] value
            int temp = DP[j];
            if (arr1[i - 1] == arr2[j - 1]) {
                DP[j] = 1 + prev;
                maxL = Math.max(maxL, DP[j]);
            }
            else {
                DP[j] = DP[j - 1];
            }
 
            // Update previous DP[j] value
            prev = temp;
        }
    }
 
    // Return final answer
    return maxL;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr1[] = { 4, 2, 3, 1, 5, 6 };
    int M = arr1.length;
 
    int arr2[] = { 3, 1, 4, 6, 5, 2 };
    int N = arr2.length;
 
    System.out.print(LongSubarrSeq(arr1, arr2, M, N));
}
}

Python3

# Function to find the length of the
# longest subarray in arr1[]
# which is a subsequence in arr2[]
def LongSubarrSeq(arr1, arr2, M, N):
    # To store the final result
    maxL = 0
     
    # To store previous computations
    # Initialize DP[] list
    DP = [0] * (N + 1)
 
    # Iterate over subproblems to get the
    # current value from previous computations
    for i in range(1, M + 1):
        prev = 0
        for j in range(1, N + 1):
            # Store current DP[j] value
            temp = DP[j]
            if arr1[i - 1] == arr2[j - 1]:
                DP[j] = 1 + prev
                maxL = max(maxL, DP[j])
            else:
                DP[j] = DP[j - 1]
 
            # Update previous DP[j] value
            prev = temp
 
    # Return the final answer
    return maxL
 
# Driver Code
if __name__ == "__main__":
    arr1 = [4, 2, 3, 1, 5, 6]
    M = len(arr1)
 
    arr2 = [3, 1, 4, 6, 5, 2]
    N = len(arr2)
 
    print(LongSubarrSeq(arr1, arr2, M, N))

Output

Time Complexity: O(M * N)
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 zambiatek!