350. Intersection of Two Arrays II

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.

Source

Code

In [1]:

from collections import Counter

def intersect(nums1, nums2):
    """
    Time Complexity:  O(n+m)
    Space Complexity: O(n+m)
    """
    counts = Counter(nums1)
    res = []
    for i in nums2:
        if counts[i] > 0:
            res += i,
            counts[i] -= 1
    return res

In [2]:

from collections import Counter

def intersect(nums1, nums2):
    """variation of above solution."""
    return list((Counter(nums1) & Counter(nums2)).elements())
    # using ".intersection()" instead of '&' (as in leetcode 350) would not work here
    # since it is a class 'set' method
    # Counter('greekgeeks').elements() = [g,g,r,e,e,e,e,k,k,s]

Check

In [3]:

nums1 = [1,2,2,1]
nums2 = [2,2]
intersect(nums1, nums2)

Out[3]:

[2, 2]

In [19]:

nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
intersect(nums1, nums2)

Out[19]:

[4, 9]

Follow up #1:

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

Code

In [8]:

 def intersect(nums1, nums2):
    """Using Two Pointers.
    Time Complexity: 0(n+m)
    Space Complexity: 0(1) (auxiliary memory, not counting output)
    """
    i, j = 0, 0
    res = []
    
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            res.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return res

Follow up #2:

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

Code

In [20]:

# It's better to construct the counter hash on nums1 - O(n) - and traverse nums2 - O(m)
# Rather than traversing nums1 - O(n) and using the Two Pointers solution on nums2
# which would require to first sort nums2 - O(mlogm)

# Time Complexity:  O(n+m)    vs O(n + mlogm)
# Space Complexity: O(n)      vs O(1)

Follow up #3:

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?

Code

In [4]:

# Answer 1
# sort nums2 using external sort, read each chunk into memory and then using the
# 2 pointer technique, Repeat this until no more data to read from disk.

# Answer 2
# If the memory is limited, you can only choose the Two Pointers method or
# the brute force method, without additional space complexity.
# When using a hash table, in the worst case, each number only appears once.
# After the HashMap element frequency is counted, its size may be larger than
# the memory capacity.

# Answer 3
# You could use the 2 pointers to keep looking up the values on disk.
# Something similar to what external merge sort does
# (https://en.wikipedia.org/wiki/External_sorting#External_merge_sort)