Intersection of Two Arrays using HashMap

In this article, we will study what is hashmap and how we can solve the problem of the intersection of two arrays using a hashmap. Also, we will go through the examples explaining the problem and its source code in python along with the corresponding output. So, let’s get started!

You can even watch the below video for a full explanation:

What is HashMap?

HashMap and Hashtable are the data structure store key/value. We can specify an object as a key and the value linked to that key using hashmap and hashtable. The key is then hashed, and the resulting hash code is used as the index at which the value is stored within the table. HashMap is non-synchronized. HashMap allows one null key and multiple null values. HashMap is generally preferred over HashTable if thread synchronization is not needed.

Intersection of Two Arrays

Problem Description: Given two integer arrays nums1[] and nums2[] of size m and n respectively. We need to find the intersection of two arrays. The result of the same is the list of distinct number which is present in both the arrays. The number of intersections can be in any order.

For example:

nums1: [10, 20, 30, 40, 50, 60]

nums2: [10, 15, 60]

result: [10, 60]

nums1: [10, 20, 30, 10, 20]

nums2: [10, 10, 15]

result: [10, 10]

Finding the intersection of two arrays using HashMap

To find the intersection of an array using a hashmap, we will make a hash map of the first array so that our searching becomes faster and all elements appear only once. Now for the other elements of the other array, we will perform a search operation of the element in the hashmap.

The algorithm of the intersection of the array using hashmap is as follow:

1. Build the hashmap for the nums1, that is, count the frequency of each element.
2. Traverse each element of nums2, one by one.
3. If the element is present in the map formed in step 1, reduce the frequency of the element by 1 and print the element, if the frequency becomes 0, remove the element from the map.
4. Repeat step 3 for all elements of nums2.

Example1:

nums1: [10, 15, 20, 25, 30]

nums2: [10, 25]

Creating the hashmap according to step 1:

Now traversing the elements of the second array and reduce the frequency according to step 3 and insert the element in the result:

Hence the result of the above is as follow:

result: [10, 25]

Example2:

nums1: [10, 15, 20, 15, 10, 25]

nums2: [65, 10, 25, 1]

Creating the hashmap according to step 1:

Increasing the frequency of 10 and 15 by one as its occurrence increases in nums1.

Now traversing the elements of the second array and reduce the frequency according to step 3 and insert the element in the result:

Hence the result of the above is as follow:

result: [10, 25]

Example3:

nums1: [10, 10, 25, 15, 15, 15, 30, 35]

nums2: [5, 6, 10, 9, 10, 15, 15]

Creating the hashmap according to step 1:

Increasing the frequency of the elements as the occurrence increases.

Now traversing the elements of the second array and reduce the frequency according to step 3 and insert the element in the result:

Hence the result of the above is as follow:

result: [10, 10, 15, 15]

Python Code for the intersection of two arrays

The code for the intersection of the two arrays in python is as given follow:

def intersection(nums1 , nums2):
    result =  []
    memo = {}

    for currentVal in nums1:

        if currentVal in memo: 
            memo[currentVal] += 1

        else:
            memo[currentVal] = 1
    
    for currentVal in nums2:

            if currentVal in memo:
                result.append(currentVal)

                memo[currentVal] -= 1

                if memo[currentVal] == 0:
                    del memo[currentVal]

    return result

nums1 = [10, 10, 25, 14, 14, 14, 56]
nums2 = [10, 10, 14, 23, 34, 56]

print(intersection(nums1, nums2))

The output of the above code is as given below:

Complexity Analysis

There are two loops to run to find the solution where the outer loop runs for m times and the inner loop runs n times. So, in the worst case, the time complexity is O(m*n). The space complexity for the worst case is O(1).

Conclusion

In the above article, we learned what a hashmap is and how to solve the intersection of two integer arrays using a hashmap. Also, we learned many examples along with the output and the python code for the intersection of arrays.