350.Intersection of Two Arrays II

Tags: [two_pointers], [sort]

Link: https://leetcode.com/problems/intersection-of-two-arrays-ii/#/description

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

Example:
Givennums1=[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?

Solution: sort, two pointers

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        if not nums1 or not nums2:
            return []

        nums1.sort()
        nums2.sort()

        size_1 = len(nums1)
        size_2 = len(nums2)

        index_1 = 0
        index_2 = 0

        result = []
        while index_1 < size_1 and index_2 < size_2:
            n1 = nums1[index_1]
            n2 = nums2[index_2]

            if n1 == n2:
                result.append(n1)
                index_1 += 1
                index_2 += 1

            elif n1 < n2:
                index_1 += 1
            else:
                index_2 += 1

        return result

Note:

• Time complexity = O(max(nlgn, klgk)), n is the length of the nums1, k is the length of the nums2.

Follow-Up:

1. If the given arrays are sorted, just use the above algorithm, the time complexity = O(min(n, k)), n is the length of the nums1, and k is the length of the nums2.
2. We can dump all elements of nums1 to a hashmap{num: counter}, then scan the nums2, to find the intersections. The reason we use hashmap is that "Each element in the result should appear as many times as it shows in both arrays".
3. We still can use the above algorithm, think that we store the sorted nums2 in the file, and maintain a file pointer (or think this is like the streaming read from a file).