Longest common subarray in the given two arrays

0 0 13 minutes read

Given two arrays A[] and B[] of N and M integers respectively, the task is to find the maximum length of an equal subarray or the longest common subarray between the two given array.

Examples:

Input: A[] = {1, 2, 8, 2, 1}, B[] = {8, 2, 1, 4, 7}
Output: 3
Explanation:
The subarray that is common to both arrays are {8, 2, 1} and the length of the subarray is 3.

Input: A[] = {1, 2, 3, 2, 1}, B[] = {8, 7, 6, 4, 7}
Output: 0
Explanation:
There is no such subarrays which are equal in the array A[] and B[].

Naive Approach: The idea is to generate all the subarrays of the two given array A[] and B[] and find the longest matching subarray. This solution is exponential in terms of time complexity.

C++

#include <iostream>
#include <vector>
using namespace std;
 
// Recursive function to find the longest common subarray (LCS)
int LCS(int i, int j, const vector<int>& A, const vector<int>& B, int count) {
    // Base case: If either of the indices reaches the end of the array, return the count
    if (i == A.size() || j == B.size())
        return count;
     
    // If the current elements are equal, recursively check the next elements
    if (A[i] == B[j])
        count = LCS(i + 1, j + 1, A, B, count + 1);
     
    // Recursively check for the longest common subarray by considering two possibilities:
    // 1. Exclude current element from array A and continue with array B
    // 2. Exclude current element from array B and continue with array A
    count = max(count, max(LCS(i + 1, j, A, B, 0), LCS(i, j + 1, A, B, 0)));
     
    return count;
}
 
int main() {
    // Example arrays
    vector<int> A = {1, 2, 3, 2, 1};
    vector<int> B = {3, 2, 1, 4, 7};
     
    // Call the LCS function to find the maximum length of the common subarray
    int maxLength = LCS(0, 0, A, B, 0);
     
    // Print the result
    cout << "Max length of common subarray: " << maxLength << endl;
     
    return 0;
}

Java

import java.util.Arrays;
import java.util.Vector;
 
public class Main {
    // Recursive function to find the longest common subarray (LCS)
    static int LCS(int i, int j, Vector<Integer> A, 
                   Vector<Integer> B, int count) {
        // Base case: If either of the indices reaches the end of the array, return the count
        if (i == A.size() || j == B.size())
            return count;
 
        // If the current elements are equal, recursively check the next elements
        if (A.get(i).equals(B.get(j)))
            count = LCS(i + 1, j + 1, A, B, count + 1);
 
        // Recursively check for the longest common subarray by considering two possibilities:
        // 1. Exclude the current element from array A and continue with array B
        // 2. Exclude the current element from array B and continue with array A
        count = Math.max(count, Math.max(LCS(i + 1, j, A, B, 0), 
                                         LCS(i, j + 1, A, B, 0)));
 
        return count;
    }
 
    public static void main(String[] args) {
        // Example arrays
        Vector<Integer> A = new Vector<>(Arrays.asList(1, 2, 3, 2, 1));
        Vector<Integer> B = new Vector<>(Arrays.asList(3, 2, 1, 4, 7));
 
        // Call the LCS function to find the maximum length of the common subarray
        int maxLength = LCS(0, 0, A, B, 0);
 
        // Print the result
        System.out.println("Max length of common subarray: " + maxLength);
    }
}
// This code is contributed by akshitaguprjz3

Python3

def LCS(i, j, A, B, count):
    # Base case: If either of the indices reaches the end of the array, 
    # return the count
    if i == len(A) or j == len(B):
        return count
     
    # If the current elements are equal, recursively check the 
    # next elements
    if A[i] == B[j]:
        count = LCS(i + 1, j + 1, A, B, count + 1)
     
    # Recursively check for the longest common subarray by considering two possibilities:
    # 1. Exclude current element from array A and continue with array B
    # 2. Exclude current element from array B and continue with array A
    return max(count, max(LCS(i + 1, j, A, B, 0), LCS(i, j + 1, A, B, 0)))
 
# Example arrays
A = [1, 2, 3, 2, 1]
B = [3, 2, 1, 4, 7]
 
# Call the LCS function to find the maximum length of the common subarray
maxLength = LCS(0, 0, A, B, 0)
 
# Print the result
print("Max length of common subarray:", maxLength)

C#

using System;
 
class GFG {
    // Recursive function to find the longest common
    // subarray (LCS)
    static int LCS(int i, int j, int[] A, int[] B,
                   int count)
    {
        // Base case: If either of the indices reaches the
        // end of the array, return the count
        if (i == A.Length || j == B.Length)
            return count;
 
        // If the current elements are equal, recursively
        // check the next elements
        if (A[i] == B[j])
            count = LCS(i + 1, j + 1, A, B, count + 1);
 
        // Recursively check for the longest common subarray
        // by considering two possibilities:
        // 1. Exclude the current element from array A and
        // continue with array B
        // 2. Exclude the current element from array B and
        // continue with array A
        count = Math.Max(count,
                         Math.Max(LCS(i + 1, j, A, B, 0),
                                  LCS(i, j + 1, A, B, 0)));
 
        return count;
    }
 
    static void Main()
    {
        // Example arrays
        int[] A = { 1, 2, 3, 2, 1 };
        int[] B = { 3, 2, 1, 4, 7 };
 
        // Call the LCS function to find the maximum length
        // of the common subarray
        int maxLength = LCS(0, 0, A, B, 0);
 
        // Print the result
        Console.WriteLine("Max length of common subarray: "
                          + maxLength);
    }
}

Output

Max length of common subarray: 3

Time Complexity: O(2^N+M), where N is the length of the array A[] and M is the length of the array B[].

Efficient Approach:
The efficient approach is to use Dynamic Programming(DP). This problem is the variation of the Longest Common Subsequence(LCS).
Let the input sequences are A[0..n-1] and B[0..m-1] of lengths m & n respectively. Following is the recursive implementation of the equal subarrays:

Since common subarray of A[] and B[] must start at some index i and j such that A[i] is equals to B[j]. Let dp[i][j] be the longest common subarray of A[i…] and B[j…].
Therefore, for any index i and j, if A[i] is equals to B[j], then dp[i][j] = dp[i+1][j+1] + 1.
The maximum of all the elements in the array dp[][] will give the maximum length of equal subarrays.

For Example:

If the given array A[] = {1, 2, 8, 2, 1} and B[] = {8, 2, 1, 4, 7}.
If the characters match at index i and j for the array A[] and B[] respectively, then dp[i][j] will be updated as 1 + dp[i+1][j+1].
Below is the updated dp[][] table for the given array A[] and B[].

Below is the implementation of the above approach:

C++

// C++ program to DP approach
// to above solution
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// length of equal subarray
int FindMaxLength(int A[], int B[], int n, int m)
{
 
    // Auxiliary dp[][] array
    int dp[n + 1][m + 1];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = 0;
 
    // Updating the dp[][] table
    // in Bottom Up approach
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            // If A[i] is equal to B[i]
            // then dp[j][i] = dp[j + 1][i + 1] + 1
            if (A[i] == B[j])
                dp[i][j] = dp[i + 1][j + 1] + 1;
        }
    }
    int maxm = 0;
 
    // Find maximum of all the values
    // in dp[][] array to get the
    // maximum length
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // Update the length
            maxm = max(maxm, dp[i][j]);
        }
    }
 
    // Return the maximum length
    return maxm;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 2, 8, 2, 1 };
    int B[] = { 8, 2, 1, 4, 7 };
 
    int n = sizeof(A) / sizeof(A[0]);
    int m = sizeof(B) / sizeof(B[0]);
 
    // Function call to find
    // maximum length of subarray
    cout << (FindMaxLength(A, B, n, m));
}
 
// This code is contributed by chitranayal

Java

// Java program to DP approach
// to above solution
class GFG 
{
    // Function to find the maximum
    // length of equal subarray
    static int FindMaxLength(int A[], int B[], int n, int m)
    {
 
        // Auxiliary dp[][] array
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                dp[i][j] = 0;
 
        // Updating the dp[][] table
        // in Bottom Up approach
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = m - 1; j >= 0; j--) 
            {
                // If A[i] is equal to B[i]
                // then dp[j][i] = dp[j + 1][i + 1] + 1
                if (A[i] == B[j])
                    dp[i][j] = dp[i + 1][j + 1] + 1;
            }
        }
        int maxm = 0;
 
        // Find maximum of all the values
        // in dp[][] array to get the
        // maximum length
        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; j < m; j++) 
            {
                // Update the length
                maxm = Math.max(maxm, dp[i][j]);
            }
        }
 
        // Return the maximum length
        return maxm;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int A[] = { 1, 2, 8, 2, 1 };
        int B[] = { 8, 2, 1, 4, 7 };
 
        int n = A.length;
        int m = B.length;
 
        // Function call to find
        // maximum length of subarray
        System.out.print(FindMaxLength(A, B, n, m));
    }
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python program to DP approach
# to above solution
 
# Function to find the maximum
# length of equal subarray
 
 
def FindMaxLength(A, B):
    n = len(A)
    m = len(B)
 
    # Auxiliary dp[][] array
    dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
 
    # Updating the dp[][] table
    # in Bottom Up approach
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
 
            # If A[i] is equal to B[i]
            # then dp[j][i] = dp[j + 1][i + 1] + 1
            if A[i] == B[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
    maxm = 0
 
    # Find maximum of all the values
    # in dp[][] array to get the
    # maximum length
    for i in dp:
        for j in i:
 
            # Update the length
            maxm = max(maxm, j)
 
    # Return the maximum length
    return maxm
 
 
# Driver Code
if __name__ == '__main__':
    A = [1, 2, 8, 2, 1]
    B = [8, 2, 1, 4, 7]
 
    # Function call to find
    # maximum length of subarray
    print(FindMaxLength(A, B))

C#

// C# program to DP approach
// to above solution
using System;
 
class GFG 
{
    // Function to find the maximum
    // length of equal subarray
    static int FindMaxLength(int[] A, int[] B, int n, int m)
    {
 
        // Auxiliary [,]dp array
        int[, ] dp = new int[n + 1, m + 1];
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                dp[i, j] = 0;
 
        // Updating the [,]dp table
        // in Bottom Up approach
        for (int i = n - 1; i >= 0; i--) 
        {
            for (int j = m - 1; j >= 0; j--)
            {
                // If A[i] is equal to B[i]
                // then dp[j, i] = dp[j + 1, i + 1] + 1
                if (A[i] == B[j])
                    dp[i, j] = dp[i + 1, j + 1] + 1;
            }
        }
        int maxm = 0;
 
        // Find maximum of all the values
        // in [,]dp array to get the
        // maximum length
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
 
                // Update the length
                maxm = Math.Max(maxm, dp[i, j]);
            }
        }
 
        // Return the maximum length
        return maxm;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] A = { 1, 2, 8, 2, 1 };
        int[] B = { 8, 2, 1, 4, 7 };
 
        int n = A.Length;
        int m = B.Length;
 
        // Function call to find
        // maximum length of subarray
        Console.Write(FindMaxLength(A, B, n, m));
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript program to DP approach
// to above solution
     
    // Function to find the maximum
    // length of equal subarray
    function FindMaxLength(A,B,n,m)
    {
        // Auxiliary dp[][] array
        let dp = new Array(n + 1);
        for (let i = 0; i <= n; i++)
        {
            dp[i]=new Array(m+1);
            for (let j = 0; j <= m; j++)
                dp[i][j] = 0;
         }
        // Updating the dp[][] table
        // in Bottom Up approach
        for (let i = n - 1; i >= 0; i--)
        {
            for (let j = m - 1; j >= 0; j--)
            {
                // If A[i] is equal to B[i]
                // then dp[i][j] = dp[i + 1][j + 1] + 1
                if (A[i] == B[j])
                    dp[j][i] = dp[j + 1][i + 1] + 1;
            }
        }
        let maxm = 0;
  
        // Find maximum of all the values
        // in dp[][] array to get the
        // maximum length
        for (let i = 0; i < n; i++)
        {
            for (let j = 0; j < m; j++)
            {
                // Update the length
                maxm = Math.max(maxm, dp[i][j]);
            }
        }
  
        // Return the maximum length
        return maxm;
    }
     
    // Driver Code
    let A=[1, 2, 8, 2, 1 ];
    let B=[8, 2, 1, 4, 7];
    let n = A.length;
    let m = B.length;
     
    // Function call to find
        // maximum length of subarray
    document.write(FindMaxLength(A, B, n, m));
     
     
     
// This code is contributed by avanitrachhadiya2155
</script>

Output

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

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 the space complexity we use only single vector dp for current row and a variable prev to get the previous computation.

Implementation Steps :

Create a vector DP of size M+1 , that stores the computation of subproblems and initialize it with 0.
Initialize a variable maxm with 0 used to store the maximum length.
Now iterative over subproblems and update the DP vector in bottom up approach.
Initialize variable prev and temp. prev is used to get the previous row value of Dp and temp is used to get the value of prev in another iteration.
While iterating update the maxm with respect to the value stored in DP.
At last return the maxm.

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// length of equal subarray
int FindMaxLength(int A[], int B[], int n, int m)
{
 
    // Auxiliary dp[] vector
    vector<int> dp(m + 1, 0);
    int maxm = 0;
 
    // Updating the dp[] vector
    // in Bottom Up approach
    for (int i = n - 1; i >= 0; i--) {
        int prev = 0;
        for (int j = m - 1; j >= 0; j--) {
            int temp = dp[j];
            if (A[i] == B[j]) {
                dp[j] = prev + 1;
                maxm = max(maxm, dp[j]);
            }
            else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }
 
    // Return the maximum length
    return maxm;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 2, 8, 2, 1 };
    int B[] = { 8, 2, 1, 4, 7 };
 
    int n = sizeof(A) / sizeof(A[0]);
    int m = sizeof(B) / sizeof(B[0]);
 
    // Function call to find
    // maximum length of subarray
    cout << (FindMaxLength(A, B, n, m));
}

Java

import java.util.Arrays;
 
public class Main {
     
    // Function to find the maximum length of equal subarray
    static int findMaxLength(int[] A, int[] B, int n, int m) {
        // Auxiliary dp[] array
        int[] dp = new int[m + 1];
        int maxm = 0;
 
        // Updating the dp[] array in Bottom Up approach
        for (int i = n - 1; i >= 0; i--) {
            int prev = 0;
            for (int j = m - 1; j >= 0; j--) {
                int temp = dp[j];
                if (A[i] == B[j]) {
                    dp[j] = prev + 1;
                    maxm = Math.max(maxm, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
 
        // Return the maximum length
        return maxm;
    }
 
    public static void main(String[] args) {
        int[] A = { 1, 2, 8, 2, 1 };
        int[] B = { 8, 2, 1, 4, 7 };
 
        int n = A.length;
        int m = B.length;
 
        // Function call to find maximum length of subarray
        System.out.println(findMaxLength(A, B, n, m));
    }
}

Python3

# code
def find_max_length(A, B, n, m):
    # Auxiliary dp[] list
    dp = [0] * (m + 1)
    maxm = 0
 
    # Updating the dp[] list
    # in Bottom Up approach
    for i in range(n - 1, -1, -1):
        prev = 0
        for j in range(m - 1, -1, -1):
            temp = dp[j]
            if A[i] == B[j]:
                dp[j] = prev + 1
                maxm = max(maxm, dp[j])
            else:
                dp[j] = 0
            prev = temp
 
    # Return the maximum length
    return maxm
 
# Driver Code
if __name__ == '__main__':
    A = [1, 2, 8, 2, 1]
    B = [8, 2, 1, 4, 7]
    n = len(A)
    m = len(B)
 
    print(find_max_length(A, B, n, m))

Javascript

// Function to find the maximum length of equal subarray
function FindMaxLength(A, B, n, m) {
    // Auxiliary dp[] vector
    let dp = new Array(m + 1).fill(0);
    let maxm = 0;
 
    // Updating the dp[] vector in Bottom Up approach
    for (let i = n - 1; i >= 0; i--) {
        let prev = 0;
        for (let j = m - 1; j >= 0; j--) {
            let temp = dp[j];
            if (A[i] == B[j]) {
                dp[j] = prev + 1;
                maxm = Math.max(maxm, dp[j]);
            } else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }
 
    // Return the maximum length
    return maxm;
}
 
let A = [1, 2, 8, 2, 1];
let B = [8, 2, 1, 4, 7];
 
let n = A.length;
let m = B.length;
 
// Function call to find maximum length of subarray
console.log(FindMaxLength(A, B, n, m));

Output

Time Complexity: O(N*M)
Auxiliary Space: O(M) , only use one vector dp of size 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!