[LeetCode] 349. Intersection of Two Arrays

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

Binary search solution: 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        
        def bsearch(nums, target):
            left, right = 0, len(nums)
            
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return True
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            
            return False
        
        result = []
        
        if len(nums1) > len(nums2) : nums1, nums2 = nums2, nums1
        
        nums1.sort()
        nums2.sort()
        
        for i, n in enumerate(nums1):
            if i - 1 >= 0 and nums1[i] == nums1[i-1]:
                continue
            
            if bsearch(nums2, n):
                result.append(n)
            
        
        return result

2 pointers solution:

class Solution:
    def intersection(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:
                if not result or result[-1] != nums1[i]:
                    result.append(nums1[i])
                i += 1
                j += 1
        
        return result

Hash table based solution:

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        seen = defaultdict(lambda : [0, 0])
        
        for n in nums1:
            seen[n][0] += 1
        
        for n in nums2:
            seen[n][1] += 1
            
        
        return filter(lambda n : seen[n][0] >= 1 and seen[n][1] >= 1, seen.keys())