Intersection Of Two Arrays Problem
Written by
Input: arr1[] = [7, 1, 5, 2, 3, 6] , arr2[] = [3, 8, 6, 20, 7]
Output: [3, 6, 7]
# Brute Force
Pseudo Code:
- Initialize intersection array as empty.
- Do following for every element x of the first array.
a. If x is present in second array, then copy x to I.
b. Return Intersection.
Code:
#include <iostream>
#include <algorithm>
using namespace std;
void intersection(int arr1[], int arr2[], int n1, int n2)
{
int i, j;
for (i = 0; i < n1; i++)
{
for (j = 0; j < n2; j++)
{
if (arr1[i] == arr2[j])
{
cout << arr1[i] << " ";
}
}
}
}
int main()
{
int arr1[] = { 3, 11, 5, 22, 42, 476, 866, 34, 23, 78, 23, 8 };
int arr2[] = { 3, 11, 6, 866, 34 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
cout << "Intersection of two arrays is n";
intersection(arr1, arr2, m, n);
return 0;
}
Space complexity : O(1)
Time complexity : O(n1*n2), where n1 is the no. of elements of the first array and n2 is no. of elements of the second array.
# Optimized Approach
Pseudo Code:
- Initialize intersection I as empty.
- Find smaller of m and n and sort the smaller array.
- For every element x of larger array, do following
a. Binary Search x in smaller array. If x is present, then copy it to I.
b. Return I.
Code:
#include <iostream> #include <algorithm> using namespace std;
int binarySearch(int arr[], int l, int r, int x); void printIntersection(int arr1[], int arr2[], int m, int n) { if (m > n) { int *tempp = arr1; arr1 = arr2; arr2 = tempp;
int temp = m; m = n; n = temp; } sort(arr1, arr1 + m); for (int i = 0; i < n; i++) if (binarySearch(arr1, 0, m - 1, arr2[i]) != -1) cout << arr2[i] << " ";
} int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x); } return -1;
} int main() { int arr1[] = { 3, 11, 5, 22, 42, 476, 866, 34, 23, 78, 23, 8 }; int arr2[] = { 3, 11, 6, 866, 34 }; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); cout << "Intersection of two arrays is n"; printIntersection(arr1, arr2, m, n); return 0; }
Output:
Intersection of two arrays is n 3, 11, 866, 34
This is how we solve the problem of Intersection of two arrays.