Problem statement

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

Solution

Similar to problem 0349, but here we can use hash-table with number of occurrences or in python we can use Counter function. The idea is to use intersection of counters, using & symbol and then just take each symbol with correct frequency. Then we use chain(*) to create list.

Complexity

It is O(n + m) for time and space where n and m are sizes of nums and nums2.

Code

class Solution:
    def intersect(self, nums1, nums2):
        return chain(*[[i]*j for i, j in (Counter(nums1) & Counter(nums2)).items()])

Follow-up

If our data is sorted, we can use two pointers approach, complexity will be O(m+n) and with additional O(1) memory, if we do not consider answer as memory. If one of arrays is much bigger than another, we can use binary search with complexity O(n log m). (note, that BS is quite tricky here, because we need to handle duplicates, we need to find the left-most matching number. Next time we perform binary search, the low should start from previously found index + 1). If nums2 is stored on disk, then we can put nums1 into hash table and use chunks of nums1. If nums1 is also big, we need to sort them, using external sort and use two pointers.