# 350. Intersection of Two Arrays II

The question asked to find to intersection of two arrays. And return the element in any order.

The first thing come into my mind is using two hashmap (dict in python) to COUNT each key's appearance. And python has a build in function Counter to do this task. After counting the appearance of each element in both arrays, we can add minimum appearance for each element to the result. Here the code:

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        c1 = Counter(nums1)
        c2 = Counter(nums2)
        ans = []
        for key in c1.keys():
            ans += [key] * min(c1[key], c2[key])
        return ans

This solution has Time Complexity of $O(2n)$.

However, after some thought, it is not necessary for us to build the second counter. Since we can travers through the second array, and for each element e in second aray, we check if Counter1[e] > 0. If true, we add e to result, and Counter1[e] = Counter1[e] - 1. If not, we move on to the next element. So we did some optimization to the previous code.

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        c1 = Counter(nums1)
        ans = []
        for element in nums2:
            if c1[element] > 0:
                ans.append(element)
                c1[element] = c1[element] - 1
        return ans