LeetCode #350 Intersection of Two Arrays II

Easy

Problem

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

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?

Solution — Hash Map

Use a hash map to save counts of all nums in nums1 and check with every nums in nums2.

Complexity

Without loss of generality, assume m and n denotes to counts of numbers in nums1 and nums2. First, it takes O(m) time to build the hash map. Then, it needs n checking to filter each elements in nums2. For each checking, it takes O(1)/O(logm) time to search and update in the hash map in average/worse cases. Therefore, its time complexity will be O(m + n)/O(m + nlogm) in average/worse cases.

For space complexity, it uses O(m) extra space for maintaining the hash map.

Solution — Two Pointers

Sort both list first, then we can solve this problem by using two pointers.

Complexity

Sort both lists take O(mlogm + nlogn) time if m and n denote to counts of numbers of nums1 and nums2. Then it takes O(m + n) time for two pointers tracking. Therefore, its time complexity will be O(mlogm + nlogn + m + n) = O(mlogm + nlogn).

It’s trivial that it uses only O(1) extra space.

Follow up

What if the given array is already sorted? How would you optimize your algorithm?

Time complexity of the two pointers approach will be O(m + n).

What if nums1’s size is small compared to nums2’s size? Which algorithm is better?

For hash map approach, its time complexity will be O(m + n)/O(m + nlogm) = O(n)/O(nlogm) with O(m) extra space in average/worst cases. For two pointers approach, its time complexity will be O(mlogm + nlogn) = O(nlogn) with O(1) extra space.

Thus, hash map approach will cost less time but two pointers approach will cost less space.

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?

In this case, it implies that n is far larger than m, which means we should let n be reduced as possible as we can. Hence, it will be better to take hash map approach because its time complexity is O(n) only.