Leetcode Intersection of Two Arrays

Tags: , , ,

Intersection of Two unsorted Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

  • Each element in the result must be unique.
  • The result can be in any order.

Analysis

Since the two arrays are unsorted, we can use HashSet to solve the problem easily.

We can also solve the problem by first sorting the two arrays, and using the algorithm of finding intersection of two sorted arrays

Java Implementation of the HashSet based algorithm

 

Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Analysis

Since there can be duplicates in the arrays, we can use a HashMap to count the frequency of the elements in num1. Then for each elements in nums2, if it is contained in the HashMap, we add it to the final result list, and update the corresponding count in the HashMap. As long as the count of an element is reduced to 0, it will be immediately removed from the HashMap. 

Java implementation:

Note that, to save space, we only store the element frequency in the HashMap for the smaller set.  This will make a big difference if one array is small, but the other array is large.  This can also solve the problem:

  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

As in this case, we don’t need to load all the elements of of the larger array (nums2) into memory.

If the arrays are sorted, we can use the idea of merging sorted list. Please refer to this post on how to get the intersection of two sorted list

Extension:

What about both nums1 and nums2 are large and stored in disk?

solution 1:

We first sort both nums1 and nums2 using external sort, then using the find intersection of sorted arrays algorithm

Solution 2:

We can divide the integer space into K disjoint buckets, then split both nums1 and nums2 into K parts respectively based on the buckets. 

For example, suppose K = 2, bucket 1 denotes negative elements, and bucket 2 denotes non-negative elements, then the elements in nums1 and nums2 are divided into two parts respectively. (e.g, nums1_part1 vs nums2_part1nums1_part2 vs nums2_part2). With the constraints that  both nums1_part1 and nums2_part2 only store negative elements; both nums1_part2 and nums2_part2 store non-negative elements. 

Then we can find the intersection between the pair of nums1_partXnums2_partX. The union of the intersections for all the pairs is the final answer. 

If K is large enough, each part of the arrays can be small enough to be loaded into memory. Then the HashSet based algorithm can be used to solve this problem.

Source:

https://leetcode.com/problems/intersection-of-two-arrays/

http://buttercola.blogspot.com/2016/06/leetcode-intersection-of-two-arrays-ii.html