# Intersection of Two Arrays  Difficulty Level Easy
Binary Search Hash Hashing Sorting Two Pointer

In intersection of two arrays problem, we have given two arrays, we need to print their intersection(common elements).

## Example  Input
arr1[] = {1, 2, 2, 1}
arr2[] = {2, 2}
Output
{2, 2}

Input
arr1 = {4, 9, 5}
arr2 = {9, 4, 9, 8, 4}
Output
{4, 9}

## Algorithm for Intersection of Two Arrays  Calculate the frequency of every element in both the arrays and select the common part, which represents the intersection of two arrays.

That is,

Consider the example,
arr1[] = {1, 2, 2, 1}
arr2[] = {2, 2}
Frequency of 1 in arr1 is 2 and of 2 in arr1 is 2.
The frequency of 2 in arr2 is 2.
So, the intersection is {2, 2}

The space used above can be optimized as follows,

1. Build the frequency map for arr1, that is, count the frequency of each element.
2. Traverse each element of arr2, one by one.
3. If the element is present in the map formed in step 1, reduce the frequency of that element by 1 and print the element, if the frequency becomes 0, remove the element from the map.
4. Repeat step 3 for all the elements of arr2.

## Explanation for Intersection of Two Arrays  Consider an example,
arr1 = {4, 9, 5}
arr2 = {9, 4, 9, 8, 4}

Tracking current Maximum Element in a Stack

Step 1

freq = {}
Iteration 1
arr1 = 4, so, freq = {(4 -> 1)}
Iteration 2
arr1 = 9, so, freq = {(4 -> 1), (9 -> 1)}
Iteration 3
arr1 = 5, so, freq = {(4 ->1), (5 -> 1), (9 -> 1)}

Step 2, 3 and 4

Iteration 1
arr2 = 9, so, freq = {(4 ->1), (5 -> 1)} and ans = {9}
Iteration 2
arr2 = 4, so, freq = {(5 -> 1)} and ans = {9, 5}
Iteration 3
arr2 = 9, so, freq = {(5 -> 1)} and ans = {9, 5}
Iteration 4
arr2 = 8, so, freq = {(5 -> 1)} and ans = {9, 5}
Iteration 5
arr2 = 4, so, freq = {(5 -> 1)} and ans = {9, 5} ## JAVA Code for Intersection of Two Arrays  ```import java.util.HashMap;

public class IntersectionOfTwoArrays {
private static void printIntersection(int[] arr1, int[] arr2) {
HashMap<Integer, Integer> map = new HashMap<>();
// Build the frequency map for arr1
for (int i = 0; i < arr1.length; i++) {
if (map.containsKey(arr1[i])) {
map.put(arr1[i], map.get(arr1[i]) + 1);
} else {
map.put(arr1[i], 1);
}
}

// Traverse the elements of arr2 one by one
for (int i = 0; i < arr2.length; i++) {
// If the map contains current element
if (map.containsKey(arr2[i])) {
// Reduce the frequency by 1
int freq = map.get(arr2[i]);
freq--;
// If freq becomes 0, remove the element from the map
if (freq == 0) {
map.remove(arr2[i]);
} else {
map.put(arr2[i], freq);
}
// Print the element
System.out.print(arr2[i] + " ");
}
}

System.out.println();
}

public static void main(String[] args) {
// Example 1
int arr1[] = new int[] {1, 2, 2, 1};
int arr2[] = new int[] {2, 2};

printIntersection(arr1, arr2);

// Example 2
int arr3[] = new int[] {4, 9, 5};
int arr4[] = new int[] {9, 4, 9, 8, 4};

printIntersection(arr3, arr4);
}
}```
```2 2
9 4```

## C++ Code for Intersection of Two Arrays  ```#include<bits/stdc++.h>
using namespace std;

void printIntersection(int *arr1, int *arr2, int n, int m) {
unordered_map<int, int> map;
// Build the frequency map for arr1
for (int i = 0; i < n; i++) {
auto it = map.find(arr1[i]);
if (it != map.end()) {
it->second = it->second + 1;
} else {
map.insert(make_pair(arr1[i], 1));
}
}

// Traverse the elements of arr2 one by one
for (int i = 0; i < m; i++) {
auto it = map.find(arr2[i]);
// If the map contains current element
if (it != map.end()) {
// Reduce the frequency by 1
it->second = it->second - 1;
// If freq becomes 0, remove the element from the map
if (it->second == 0) {
map.erase(arr2[i]);
}
// Print the element
cout<<arr2[i]<<" ";
}
}
cout<<endl;
}

int main() {
// Example 1
int arr1[] = {1, 2, 2, 1};
int arr2[] = {2, 2};

printIntersection(arr1, arr2, sizeof(arr1)/ sizeof(arr1),
sizeof(arr2) / sizeof(arr2));

// Example 2
int arr3[] = {4, 9, 5};
int arr4[] = {9, 4, 9, 8, 4};

printIntersection(arr3, arr4, sizeof(arr3) / sizeof(arr3),
sizeof(arr4) / sizeof(arr4));
}```
```2 2
9 4```

## Complexity Analysis  Time Complexity = O(n + m)
Space Complexity = O(n)
where n is the length of arr1 and m is the length of arr2.