350.intersection-of-two-arrays-ii.md

350. Intersection of Two Arrays II

Hash Table

Idea!! Count the occurrence of every elements in both arrays, and iterate the unique elements to find the common part. For example, [1, 2, 3, 2, 4] and [2, 2, 2, 3, 3], we will get count1 = {1: 1, 2: 2, 3: 1, 4: 1} and count2 = {2: 3, 3: 2}. Then we iterate count1 and find the common part = min(count1[key], count2[key]).

value   count1  count2  common
1     =     1       0        0
2     =     2       3        2
3     =     1       2        1
4     =     1       0        0

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
    if len(nums1) > len(nums2):
        return self.intersect(nums2, nums1)

    count = {}
    for n in nums1:
        count[n] = count.get(n, 0) + 1

    intersection = []
    for n in nums2:
        if n in count and count[n] > 0:
            intersection.append(n)
            count[n] -= 1
    return intersection

# (Might skip) Or equivalently, we count two hash tables, and iterate the unique elements to find the common part.
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
    count1 = {}
    count2 = {}
    for n in nums1:
        count1[n] = count1.get(n, 0) + 1
    for n in nums2:
        count2[n] = count2.get(n, 0) + 1

    intersection = []
    for key in count1.keys():
        common_freq = min(count1.get(key, 0), count2.get(key, 0))
        if common_freq:
            for i in range(common_freq):
                intersection.append(key)
    return intersection

fun intersect(nums1: IntArray, nums2: IntArray): IntArray {
    // We will build hash table on the array with
    // shorter length, but it's not necessary.
    if (nums1.size > nums2.size) return intersect(nums2, nums1)

    val hashTable = hashMapOf<Int, Int>()
    for (i in 0 until nums1.size) {
        hashTable[nums1[i]] = (hashTable[nums1[i]] ?: 0) + 1
    }
    val results = mutableListOf<Int>()
    for (j in 0 until nums2.size) {
        if (hashTable.containsKey(nums2[j])) {
            val count = hashTable[nums2[j]]!!
            if (count > 0)) {
                results.add(nums2[j])
                hashTable[nums2[j]] = count - 1
            }
        }
    }
    return results.toIntArray()
}

• Time Complexity: O(m + n).
• Space Complexity: O(min(m, n)) for hash table.

Two Pointers

Or we can sort both the arrays, then use two pointers to find the common part.

[1, 2, 2, 3, 4] // nums1
 *
[2, 2, 2, 3, 3] // nums2
 *

• If the two pointers point to the same value, then we found the common part, and move both pointers.
• If the two pointers point to different values, then move the pointer that points to the smaller value.

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
    nums1.sort()
    nums2.sort()

    n1 = 0
    n2 = 0
    intersection = []
    while n1 < len(nums1) and n2 < len(nums2):
        if nums1[n1] == nums2[n2]:
            intersection.append(nums1[n1])
            n1 += 1
            n2 += 1
        elif nums1[n1] < nums2[n2]:
            n1 += 1
        else:
            n2 += 1
    return intersection

fun intersect(nums1: IntArray, nums2: IntArray): IntArray {
    nums1.sort()
    nums2.sort()

    val results = mutableListOf<Int>()
    var index1 = 0
    var index2 = 0
    while (index1 < nums1.size && index2 < nums2.size) {
        if (nums1[index1] < nums2[index2]) index1++
        else if (nums1[index1] > nums2[index2]) index2++
        else {
            // Common part
            // [2, 2] / [2, 2, 2, 2] or reverse
            results.add(nums1[index1])
            index1++
            index2++
        }
    }

    return results.toIntArray()
}

• Time Complexity: O(m * log m + n * log n).
• Space Complexity: O(log m + log n + min(m, n)) for sorting and result.

Follow-up

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

If the arrays are sorted, then two pointers approache will be optimal, time complexity: O(m + n) and space complexity: O(1).

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

If we know the size of one of the arrays is smaller, then we can use hash table on the smaller array which give us better space complexity: O(min(m, n)).

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?

Once we can't load all elements into the memory at once, we can't sort the array. We can use hash table to build the frequency on the smaller array (the only thing we need to load all into memory), then streaming another array in chunks to compare with hash table.