Intersection of Two Arrays II Leetcode Solution

Table of Contents

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.

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.

Lets visualize using an example in figure below: