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

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()
}

// Or equivalently, but space complexity is O(m + n)
fun intersect(nums1: IntArray, nums2: IntArray): IntArray {
    val count1 = HashMap<Int, Int>()
    val count2 = HashMap<Int, Int>()

    for (num in nums1) count1[num] = (count1[num] ?: 0) + 1
    for (num in nums2) count2[num] = (count2[num] ?: 0) + 1

    val results = mutableListOf<Int>()
    for (key in count1.keys) {
        var intersectionCount = minOf(count1[key]!!, count2[key] ?: 0)
        for (i in 0 until intersectionCount) {
            results.add(key)
        }
    }
    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 lg m + n lg n).
• Space Complexity: O(min(m, n)) for result.

Follow-up

• 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.

• 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, and iterate the larger array to find the common part. This will give us better space complexity.

• 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?

If we can't load all elements into the memory at once, then we can't sort the array, then we consider the hash table approach.

TODO: https://leetcode.com/problems/intersection-of-two-arrays-ii/solutions/1468295/python-2-approaches-3-follow-up-questions-clean-concise/