Intersection of Two Arrays II Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Facebook Google Oracle
algorithms coding HashMap Interview interviewprep LeetCode LeetCodeSolutions Sorting Two Pointers

Problem Statement

In this problem two arrays are given and we have to find out the intersection of this two arrays and return the resultant array.
Each element in the result should appear as many times as it shows in both arrays. The result can be in any order.

Example

nums1 = [1,2,2,1], nums2 = [2,2]
[2,2]
nums1 = [4,9,5], nums2 = [9,4,9,8,4]
[4,9]

Approach 1 (Using Hash map)

To find out the intersection of two arrays (nums1 and nums2) we can first store the count of each element of one array (let nums1) using a Hash map. Then we can traverse through the second array (nums2) and for each element in nums2 we would check if count of that element in nums1 is positive or not.

  • if count of nums2[i] in array nums1 is positive, then add this element(nums2[i]) in result array. And decrease the count of this element in Hash map.
  • else this element is not to be added in result.

Note: we will store the elements of that array in hash map whose size is smaller so as to minimize the space complexity.

See also
Maximum Number of Coins You Can Get Leetcode Solution

Implementation for Intersection of Two Arrays II Leetcode Solution

C++ Program

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

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

    if(nums1.size()>nums2.size()){
        swap(nums1,nums2);
    }

    unordered_map< int , int >  m;
    for(auto val:nums1){
        m[val]++;
    }

    int k=0;
    for(auto val:nums2){
        if(m[val]>0){
            nums1[k++]=val;
            --m[val];
        }
    }

    return vector<int>(nums1.begin(),nums1.begin()+k);

}

int main() 
{
    vector<int> nums1={1,2,2,1};
    vector<int> nums2={2,2};
    vector<int> ans=intersect(nums1,nums2);
    for(int x:ans)
        cout<<x<<" ";
   return 0; 
}
[2,2]

Java Program

import java.util.*;
class Rextester{
    
    public static int[] intersect(int[] nums1, int[] nums2)
    {
        if(nums1.length>nums2.length){
            return intersect(nums2,nums1);
        }

        Map<Integer,Integer>  m= new HashMap<Integer,Integer>();
        for(int val:nums1){
            m.put(val,m.getOrDefault(val,0)+1);
        }

        int k=0;
        for(int val:nums2){
            if(m.getOrDefault(val,0)>0){
                nums1[k++]=val;
                m.put(val,m.get(val)-1);
            }
        }

        int ans[]=new int[k];
        for(int i=0;i<k;i++){
            ans[i]=nums1[i];
        }

        return ans;
    }
    
  public static void main(String args[])
    {
        int[] nums1={1,2,2,1};
        int[] nums2={2,2};
    int[] ans=intersect(nums1,nums2);
        for(int x:ans)
            System.out.print(x+" ");
    }
}
[2,2]

Complexity Analysis for Intersection of Two Arrays II Leetcode Solution

Time Complexity

O(n+m): Where n and m are lengths of the array. We iterate linearly through both the arrays and insert and fetch operation in hash map takes constant time.

Space Complexity 

O(min(n,m)): We use hash map to store the elements of the smaller array.

Approach 2 (Using Two Pointers)

If the elements of both the array is sorted then this approach is more efficient. For this problem as it is not sorted we sort both the arrays first.
Now we will use two pointers i and j for the two arrays and initialize both with zero.
Move index i along 1st array(nums1) and index j along 2nd array(nums2)

  • Compare the two elements pointed by i and j.
  • If nums1[i] is less than nums2[j] then we know that we have to leave the smaller element and go to next(greater) element in nums1 array so as to check for intersection of elements.
  • Else if nums1[i] is greater than nums2[j] then similarly we have to go to next(greater) element in nums2 array.
  • Else both the elements intersected, hence add this element to result array. And Increment both i and j.
See also
Dynamic Programming Basics

Lets visualize using an example in figure below:

Intersection of Two Arrays II Leetcode SolutionPin

 

Implementation for Intersection of Two Arrays II Leetcode Solution

C++ Program

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

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) 
{
    sort(nums1.begin(),nums1.end());
    sort(nums2.begin(),nums2.end());

    int i=0,j=0,k=0;
    while(i<nums1.size() && j<nums2.size())
    {
        if(nums1[i]<nums2[j]) i++;
        else if(nums1[i]>nums2[j]) j++;
        else{
            nums1[k++]=nums1[i];
            ++i,++j;
        }
    }

    return vector<int>(nums1.begin(),nums1.begin()+k);
}

int main() 
{
    vector<int> nums1={1,2,2,1};
    vector<int> nums2={2,2};
    vector<int> ans=intersect(nums1,nums2);
    for(int x:ans)
        cout<<x<<" ";
   return 0; 
}
[2,2]

Java Program

import java.util.*;
class Rextester{
    
    public static int[] intersect(int[] nums1, int[] nums2)
    {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i=0,j=0,k=0;
        while(i<nums1.length && j<nums2.length)
        {
            if(nums1[i]<nums2[j]) i++;
            else if(nums1[i]>nums2[j]) j++;
            else{
                nums1[k++]=nums1[i];
                ++i;++j;
            }
        }
        
        int ans[]=new int[k];
        for(i=0;i<k;i++){
            ans[i]=nums1[i];
        }

        return ans;    
    }
    
  public static void main(String args[])
    {
        int[] nums1={1,2,2,1};
        int[] nums2={2,2};
    int[] ans=intersect(nums1,nums2);
        for(int x:ans)
            System.out.print(x+" ");
    }
}
[2,2]

Complexity Analysis for Intersection of Two Arrays II Leetcode Solution

Time Complexity

O(logn+logm): We sort both the arrays whose size is n and m. And then we iterate linearly on both the arrays.

Space Complexity 

O(max(logn,logm)) to O(max(n,m)): It depends on sorting algorithm we used.

1