[LeetCode] 350. Intersection of Two Arrays II

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

2 pointers solution:  

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

When elements are stored on disk, use external sort algorithm to sort items first. Then use this 2 pointers approach to find the intersection.

Hash table based solutin:

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        counter1 = Counter(nums1)
        counter2 = Counter(nums2)
        
        result = []
        
        for k, v1 in counter1.items():
            v2 = counter2.get(k, 0)
            
            if min(v1, v2):
                result += [k] * min(v1, v2)
        
        return result

Edited on 09/17/2021. Update a simpler hash table based solution.