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 arraysA = [1, 2, 3, 2, 1]B = [3, 2, 1, 4, 7]# Call the LCS function to find the maximum length of the common subarraymaxLength = LCS(0, 0, A, B, 0)# Print the resultprint("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(2N+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 subarrayint 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 Codeint 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 solutionclass 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 subarraydef 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 Codeif __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 solutionusing 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
3
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 subarrayint 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 Codeint 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
# codedef 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 Codeif __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 subarrayfunction 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 subarrayconsole.log(FindMaxLength(A, B, n, m)); |
Output
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
