Intersection of Two Arrays

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}

Step 1

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

Step 2, 3 and 4

Iteration 1
arr2[0] = 9, so, freq = {(4 ->1), (5 -> 1)} and ans = {9}
Iteration 2
arr2[1] = 4, so, freq = {(5 -> 1)} and ans = {9, 5}
Iteration 3
arr2[2] = 9, so, freq = {(5 -> 1)} and ans = {9, 5}
Iteration 4
arr2[3] = 8, so, freq = {(5 -> 1)} and ans = {9, 5}
Iteration 5
arr2[4] = 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[0]), 
            sizeof(arr2) / sizeof(arr2[0]));
            
    // Example 2
    int arr3[] = {4, 9, 5};
    int arr4[] = {9, 4, 9, 8, 4};
    
    printIntersection(arr3, arr4, sizeof(arr3) / sizeof(arr3[0]), 
            sizeof(arr4) / sizeof(arr4[0]));
}

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.

References