Given two arrays A and B of the same length N, filled with a permutation of natural numbers from 1 to N, the task is to count the number of common subarrays in A and B.
Examples:
Input: A = [1, 2, 3], B = [2, 3, 1]
Output: 4
Explanation:
The common subarrays are [1], [2], [3], [2, 3]
Hence, total count = 4
Input: A = [1, 2, 3, 4, 5], B = [2, 3, 1, 4, 5]
Output: 7
Explanation:
The common subarrays are [1], [2], [3], [4], [5], [2, 3], [4, 5]
Hence, total count = 7
Naive Approach:
The idea is to generate all subarrays of A and B separately, which would take O(N2) for each array. Now, compare all subarrays of A with all subarrays of B and count common subarrays. It would take O(N4).
Efficient Approach:
The idea is to use Hashing to solve this problem efficiently.
- Create a Hash array H of size N+1.
- Represent all elements of A by their respective indices:
Element Representation A[0] 0 A[1] 1 A[2] 2 . . and so on.
3. Use array H to store this representation, H[ A[ i ] ] = i
4. Update the elements of B according to this new representation using H, B[ i ] = H[ B[ i ] ]
5. Now, array A can be represented as [0, 1, 2, ..N], so simply count number of subarrays in B which have consecutive elements. Once we get length K of subarray of consecutive elements, count total possible subarray using following relation:
Total number of subarrays = (K * (K + 1)) / 2
Look at this example to understand this approach in detail:
Example:
A = [4, 3, 1, 2, 5]
B = [3, 1, 2, 4, 5]
Common subarrays are [1], [2], [3], [4], [5], [3, 1], [1, 2], [3, 1, 2] = 8
1. Represent A[i] as i, and store in H as H[A[i]] = i, Now array H from index 1 to N is,
H = [2, 3, 1, 0, 4]
2. Update B according to H, B[i] = H[B[i]]
B = [1, 2, 3, 0, 4]
3. Look for subarray in B with consecutive elements,
Subarray from index 0 to 2 is [1, 2, 3], consisting of consecutive elements with length K = 3
Element at index 3 forms a subarray [0] of length K = 1
Element at index 4 forms a subarray [4] of length K = 1
4. Total number of common subarrays =
(3*(3+1))/2 + (1*(1+1))/2 + (1*(1+1))/2 = 6 + 1 + 1 = 8
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include<bits/stdc++.h> using namespace std; int commonSubarrays(int *A, int *B, int N){ // Initialising Map for // Index Mapping int Map[N + 1]; // Mapping elements of A for(int i = 0 ; i< N; i++) Map[*(A + i)] = i; // Modify elements of B // according to Map for (int i = 0; i < N; i++) { // Changing B[i] as // the index of B[i] in A *(B + i) = Map[*(B + i)]; } // Count of common subarrays int count = 0; // Traversing array B int i = 0, K; while (i < N) { K = 1; i+= 1; // While consecutive elements // are found, we increment K while (i < N && B[i] == B[i - 1] + 1) { i += 1; K += 1; } // Add number of subarrays //with length K // to total count count = count + ((K) * (K + 1)) / 2; } return count; } // Driver code int main() { int N = 3; int A[] = {1, 2, 3}; int B[] = {2, 3, 1}; cout << (commonSubarrays(A, B, N)) << endl; N = 5; int C[] = {1, 2, 3, 4, 5}; int D[] = {2, 3, 1, 4, 5}; cout << (commonSubarrays(C, D, N));}// This code is contributed by chitranayal |
Java
// Java implementation of the above approachclass GFG{ static int commonSubarrays(int []A, int []B, int N){ // Initialising Map for // Index Mapping int []Map = new int[N + 1]; // Mapping elements of A for(int i = 0; i< N; i++) Map[A[i]] = i; // Modify elements of B // according to Map for(int i = 0; i < N; i++) { // Changing B[i] as // the index of B[i] in A B[i] = Map[B[i]]; } // Count of common subarrays int count = 0; // Traversing array B int i = 0, K; while (i < N) { K = 1; i+= 1; // While consecutive elements // are found, we increment K while (i < N && B[i] == B[i - 1] + 1) { i += 1; K += 1; } // Add number of subarrays //with length K // to total count count = count + ((K) * (K + 1)) / 2; } return count; } // Driver code public static void main(String[] args) { int N = 3; int A[] = {1, 2, 3}; int B[] = {2, 3, 1}; System.out.print(commonSubarrays(A, B, N)); System.out.print("\n"); N = 5; int C[] = {1, 2, 3, 4, 5}; int D[] = {2, 3, 1, 4, 5}; System.out.print(commonSubarrays(C, D, N));}}// This code is contributed by gauravrajput1 |
Python3
# Python3 implementation of above approachdef commonSubarrays(A, B, N): # Initialising Map for # Index Mapping Map = [0 for i in range(N + 1)] # Mapping elements of A for i in range(N): Map[A[i]]= i # Modify elements of B # according to Map for i in range(N) : # Changing B[i] as # the index of B[i] in A B[i]= Map[B[i]] # Count of common subarrays count = 0 # Traversing array B i = 0 while i<N: K = 1 i+= 1 # While consecutive elements # are found, we increment K while i<N and B[i]== B[i-1]+1: i+= 1 K+= 1 # Add number of subarrays # with length K # to total count count = count + ( (K)*(K + 1))//2 return count # Driver codeN = 3A =[1, 2, 3]B =[2, 3, 1]print(commonSubarrays(A, B, N))N = 5A =[1, 2, 3, 4, 5]B =[2, 3, 1, 4, 5]print(commonSubarrays(A, B, N)) |
C#
// C# implementation of the above approachusing System;class GFG{ static int commonSubarrays(int []A, int []B, int N){ // Initialising Map for // Index Mapping int []Map = new int[N + 1]; // Mapping elements of A for(int i = 0; i < N; i++) Map[A[i]] = i; // Modify elements of B // according to Map for(int i = 0; i < N; i++) { // Changing B[i] as // the index of B[i] in A B[i] = Map[B[i]]; } // Count of common subarrays int count = 0; // Traversing array B int a = 0, K; while (a < N) { K = 1; a += 1; // While consecutive elements // are found, we increment K while (a < N && B[a] == B[a - 1] + 1) { a += 1; K += 1; } // Add number of subarrays //with length K // to total count count = count + ((K) * (K + 1)) / 2; } return count; } // Driver code public static void Main() { int N = 3; int []A = {1, 2, 3}; int []B = {2, 3, 1}; Console.Write(commonSubarrays(A, B, N)); Console.Write("\n"); N = 5; int []C = {1, 2, 3, 4, 5}; int []D = {2, 3, 1, 4, 5}; Console.Write(commonSubarrays(C, D, N));}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript implementation of the above approachfunction commonSubarrays(A, B, N){ // Initialising Map for // Index Mapping let Map = Array.from({length: N+1}, (_, i) => 0); // Mapping elements of A for(let i = 0; i< N; i++) Map[A[i]] = i; // Modify elements of B // according to Map for(let i = 0; i < N; i++) { // Changing B[i] as // the index of B[i] in A B[i] = Map[B[i]]; } // Count of common subarrays let count = 0; // Traversing array B let i = 0, K; while (i < N) { K = 1; i+= 1; // While consecutive elements // are found, we increment K while (i < N && B[i] == B[i - 1] + 1) { i += 1; K += 1; } // Add number of subarrays //with length K // to total count count = count + ((K) * (K + 1)) / 2; } return count; } // Driver Code let N = 3; let A = [1, 2, 3]; let B = [2, 3, 1]; document.write(commonSubarrays(A, B, N)); document.write("<br/>"); N = 5; let C = [1, 2, 3, 4, 5]; let D = [2, 3, 1, 4, 5]; document.write(commonSubarrays(C, D, N)); // This code is contributed by target_2. </script> |
4 7
Time complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!