Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
2.1.
Example
3.
Hashing Approach
3.1.
Code
3.1.1.
Input
3.1.2.
Output
3.2.
Time Complexity
3.3.
Space Complexity
4.
Two Pointer Approach
4.1.
Code
4.1.1.
Input
4.1.2.
Output
4.2.
Time Complexity
4.3.
Space Complexity
5.
Frequently asked questions
6.
Conclusion
Last Updated: Mar 27, 2024

Intersection of Two Arrays

Author Saksham Gupta
3 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Arrays are the foundation of every coding interview. As a result, having a solid understanding of the subject is critical. But don't be concerned about anything. Ninjas are here to help, and today we'll tackle the well-known interview question 'Intersection of two arrays.' The concept of two pointers is central to the intersection of two arrays question. So, let's take a look at the question's problem statement, 'Intersection of two arrays.'

Also see, Euclid GCD Algorithm

Understanding the Problem

You've been given two arrays, 'A' and 'B,' each of which is of size 'N' and 'M,' respectively. These two arrays are sorted in ascending order. You must find the point where these two arrays intersect.

The intersection of two arrays is an array that contains all of the elements that are common to both arrays.

Example

Input

A= [1 2 2 2 3 4]

B= [2 2 3 3]

Output

2 2 3

Explanation: In both arrays, the common elements are 2 2 3, so we print them.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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;
}

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!

Previous article
Suffix Array Optimal Construction
Next article
Sliding Window
Live masterclass