Intersection of Two Arrays

Hashing Approach

Using a map to find common elements is the simplest way to solve this problem.

To begin, we can create a map by hashing all of the elements from the first array.

Now we iterate through the second array to see if the same elements are present in the map; if they are, we print them; otherwise, we continue.

We'll have all the common elements from both arrays at the end of this loop.

Code

#include<bits/stdc++.h>
using namespace std;


vector<int> findArrayIntersection(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    // Declare an array to store answer.
    vector<int> ans;

    unordered_map<int, int> mp;

    // Hashing the elements of the first array
    for (int i = 0; i < n; i++)
    {
        mp[arr1[i]]++;
    }

    for (int j = 0; j < m; j++)
    {
        // Checking if the elements are present in the second array or not.
        if (mp.count(arr2[j]) != 0)
        {
            ans.push_back(arr2[j]);
            mp[arr2[j]]--;

            // Deleting the element if it's frequency is 0.
            if (mp[arr2[j]] == 0)
            {
                mp.erase(arr2[j]);
            }
        }
    }

    return ans;
}

int main() {
    int n;
    cin>>n;
    int m;
    cin>>m;
    vector<int>a(n);
    vector<int>b(m);
   
    for(int i=0;i<n;i++)
    {
        int ele;
        cin>>ele;
        a[i]=ele;
    }
   
    for(int i=0;i<m;i++)
    {
        int ele;
        cin>>ele;
        b[i]=ele;
    }
   
    vector<int>ans= findArrayIntersection(a,n,b,m);
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i]<<" ";
    }
   
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

6 4
1 2 2 2 3 4
2 2 3 3

Output

2 2 3

Time Complexity

O(N+M), where ‘N’ is the size of the first array and ‘M’ is the size of the second array.

Explanation: We are traversing both arrays. Therefore time complexity is O(N+M)

Space Complexity

O(N), where N is the size of the first array.

Explanation: We are using a map which makes the space complexity O(N)

Two Pointer Approach

• To solve this problem, we can use two pointers. The use of two pointers is based on the fact that the arrays are sorted.
• Let i be the pointer to the first array, and let i = 0.
• Let j be the second pointer to another array, and let j = 0.
• Now, while I N and j M, run the loop: if(arr[i] == brr[j]), then the elements are the same, so print arr[i] and do j = j + 1, i = i + 1.
• If (arr[i] > brr[j]), set j = j + 1 because we've already processed a greater element in arr.
• Otherwise, use the formula i = i + 1.
• We'll have the common elements from both arrays at the end of this loop.

Code

#include<bits/stdc++.h>
using namespace std;

vector<int> findArrayIntersection(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    // Declare an array to store answer.
    vector<int> ans;

    int i = 0;
    int j = 0;

    while (i < n && j < m)
    {
        // If both the elements are equal then we increase both the pointers.
        if (arr1[i] == arr2[j])
        {
            ans.push_back(arr1[i]);
            i++;
            j++;
        }
       
        // If element of first array is greater, increment 'j'
        else if (arr1[i] > arr2[j])
        {
            j++;
        }
       
        // Otherwise increment 'i'
        else
        {
            i++;
        }
    }

    // Return 'ans'
    return ans;
}

int main() {
    int n;
    cin>>n;
    int m;
    cin>>m;
    vector<int>a(n);
    vector<int>b(m);
   
    for(int i=0;i<n;i++)
    {
        int ele;
        cin>>ele;
        a[i]=ele;
    }
   
    for(int i=0;i<m;i++)
    {
        int ele;
        cin>>ele;
        b[i]=ele;
    }
   
    vector<int>ans= findArrayIntersection(a,n,b,m);
    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i]<<" ";
    }
   
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

6 4
1 2 2 2 3 4
2 2 3 3

Output

2 2 3

Time Complexity

O(N+M), where ‘N’ is the size of the first array and ‘M’ is the size of the second array.

Explanation: We are traversing both arrays. Therefore time complexity is O(N+M)

Space Complexity

O(N), where N is the size of the first array.

Explanation: We are using a map that makes the space complexity O(N)

Frequently asked questions

1. What is an array?
   An array data structure, or simply an array, is a data structure in computer science that consists of a collection of elements, each of which is identified by at least one array index or key. An array is stored in such a way that the position of each element can be calculated using a mathematical formula from its index tuple.
    
2. What is two pointer technique?
   Two-pointer is a simple and effective technique that is commonly used to find pairs in a sorted array. It solves the problem in linear time, but it only applies to sorted arrays. 
    
3. What is meant by the intersection of two arrays?
   If we are given two arrays, then the intersection of them represents the elements that are common to both the arrays and thus named the intersection of two arrays
    
4. What questions other than the intersection of two arrays use the two-pointer technique?
   Questions other than the intersection of two arrays that uses the two-pointer technique are rainwater tapping, sum problems such as finding pairs whose sum equals x or triplets whose sum equals x, etc.
    
5. Are there any other Data Structures and Algorithms content in Coding Ninjas Studio?
   Yes, you can practice coding while also answering common interview questions with Coding Ninjas Studio. The more we practice, the more likely we are to get a job at our dream company.

Conclusion

In this article, we have extensively discussed the problem of the ‘Intersection of two arrays.’ We saw all two methods to solve the problem ‘Intersection of two arrays”. We hope that this blog has helped you enhance your knowledge of ‘Intersection of two arrays’ and if you would like to learn more, check out our articles on Library. Do upvote our blog to help other ninjas grow. Happy Coding!