import collections

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        i, j = 0, 0
        res = []
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                res.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return res


class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums2_count = collections.Counter(nums2)
        res = []
        for num in nums1:
            if num in nums2_count and nums2_count[num] > 0:
                res.append(num)
                nums2_count[num] -= 1
        return res

res = Solution().intersect([1],[1])
print(res) # [1]

res = Solution().intersect([1,2,2,1],[2,2])
print(res) # [2,2]

# follow up 2
# What if nums1's size is small compared to nums2's size? Which algorithm is better?
# put all elements of nums2 into a hashmap, iterate through nums1 to get intersection

# follow up 3
# 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 only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
# If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.