350 Intersection of Two Arrays II

We are required to count and return occurences of elements that are present in both arrays.

Code

Python3

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
 
    c1 = Counter(nums1)
    c2 = Counter(nums2)
 
    res = []
 
    for a in nums1:
        if a in c1 and a in c2:
            c1[a] -= 1
            c2[a] -= 1
            res.append(a)
 
            if c1[a] == 0:
                del c1[a]
            if c2[a] == 0:
                del c2[a]
 
    return res

Big O Analysis

• Runtime

  The runtime complexity here is $O(N)$ since we are visiting all elements in the array only once.

• Memory

  The memory usage is $O(N)$ since we use the collections.Counter object to store frequencies.

— A

GitHub | Twitter