Intersection of 2 arrays Algorithm
The Intersection of 2 Arrays Algorithm is a technique used to find common elements between two given arrays or lists. This algorithm is useful in various applications, such as data analysis, database querying, and set operations. The main idea behind this algorithm is to compare each element of one array with the elements of the other array and identify the common elements between the two. There are multiple ways to implement this algorithm, such as using nested loops, sorting and merging, or using hash maps to achieve this goal with different time and space complexities.
One common approach to implement the Intersection of 2 Arrays Algorithm is by using nested loops, wherein the outer loop iterates through the elements of the first array, and the inner loop iterates through the elements of the second array. If an element from the first array matches an element from the second array, it is added to the result set. Although this approach is simple and easy to understand, it has a time complexity of O(n*m), where n and m are the lengths of the two arrays. Alternatively, a more efficient approach is to use a hash map to store the frequency of elements in the first array and then iterate through the second array, checking if the element exists in the hash map. If it does, it is added to the result set and the frequency is reduced by one. This approach has a time complexity of O(n+m) and a space complexity of O(min(n, m)), making it a more efficient solution for larger datasets.
#include <iostream>
int main()
{
int i, j, m, n;
cout << "Enter size of array 1:";
cin >> m;
cout << "Enter size of array 2:";
cin >> n;
int a[m];
int b[n];
cout << "Enter elements of array 1:";
for (i = 0; i < m; i++)
cin >> a[i];
for (i = 0; i < n; i++)
cin >> b[i];
i = 0;
j = 0;
while ((i < m) && (j < n))
{
if (a[i] < b[j])
i++;
else if (a[i] > b[j])
j++;
else
{
cout << a[i++] << " ";
j++;
}
}
return 0;
}
