# https://leetcode.com/problems/intersection-of-two-arrays-ii
from typing import Dict, List


class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        s1: Dict[int, int] = {}
        s2: Dict[int, int] = {}
        ret: List[int] = []
        for v in nums1:
            if s1.get(v) == None:
                s1[v] = 1
            else:
                s1[v] += 1
        for v in nums2:
            if s2.get(v) == None:
                s2[v] = 1
            else:
                s2[v] += 1
        f = len(s1) > len(s2)
        loop: Dict[int, int] = s2 if f else s1
        another = s1 if f else s2
        for key in loop.keys():
            if another.get(key) == None:
                continue
            while loop[key] > 0 and another[key] > 0:
                loop[key] -= 1
                another[key] -= 1
                ret.append(key)
        return ret