350_Intersection of Two Arrays II

[Easy][Array, Two Pointers, Binary Search, Hash Table, Sort]

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

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?

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]

Solution 1: Sort + Binary Search

Idea:

• Sort the two arrays first.

• Loop over each element in one array, use binary search to find if that element exist in the other array.

• We can choose smaller length array for the loop, such that the time complexity will be smaller.

• This approach has advantage if one array is much smaller in size than the other one.

Time Complexity: $O(m \log{n})$ or $O(n\log{m})$

Space Complexity: $O(1)$

def intersect(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    # sort two arrays
    nums1.sort()
    nums2.sort()

    def is_present(a):
        # get the location to insert a into nums2 
        # on the left of any existing entries
        import bisect
        i = bisect.bisect_left(nums2, a)
        if i < len(nums2) and nums2[i] == a:
            nums2.pop(i)
            return True
        else:
            return False

        return [a for i, a in enumerate(nums1) if is_present(a)]

Solution 2: Sort + Two Pointers

Idea:

• First sort the two arrays.

• Simultaneously advance through the two arrays in increasing order. At each iteration:

  • If the two elements differ, eliminate the small one.

  • If they are the same, append to output and advance both.

• If the length of two arrays are similar, this solution has advantage.

Time Complexity: $O(m \log{m} + n \log{n} + m + n)$

Space Complexity: $O(1)$

def intersect(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    # sort two arrays
    nums1.sort()
    nums2.sort()

    # two pointers
    p1, p2 = 0, 0
    output = []
    while p1 < len(nums1) and p2 < len(nums2):
        if nums1[p1] > nums2[p2]:
            p2 += 1
        elif nums1[p1] < nums2[p2]:
            p1 += 1
        else:
            output.append(nums1[p1])
            p1 += 1
            p2 += 1
    return output

Solution 3: Dictionary

Idea:

• Count frequency of each number in nums1, store in a dictionary.

• Loop for each element in nums2, check if it has a pair in the dictionary. If yes, append the element, and decrease the corresponding frequency by 1.

Time Complexity: $O(m+n)$

Space Complexity: $O(m)$ or $O(n)$, can choose the smaller one.

def intersect(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    counts = {}
    output = []
    # count frequency of each number in nums1
    for num in nums1:
        counts[num] = counts.get(num, 0) + 1
    # check if each number in nums2 has a pair
    for num in nums2:
        if num in counts and counts[num] > 0:
            output.append(num)
            counts[num] -= 1
    return output