350 Intersection of Two Arrays II

[tech-cow]

Redo Binary Search, has bug

349. Intersection of Two Arrays

class Solution(object):
    def intersection(self, nums1, nums2):
        nums1 = set(nums1)
        nums2 = set(nums2)
        res = []
        
        for num in nums1:
            if num in nums2:
                res.append(num)
        return res

Follow up

350 Intersection of Two Arrays II

Bugfree in 3 mins using 2 pointers. Pretend the arrays are sorted.
Time: O(N) if array given are sorted
Space: O(1)

class Solution(object):
    def intersect(self, nums1, nums2):
        nums1.sort()
        nums2.sort()
        
        i, j = 0, 0
        m, n = len(nums1), len(nums2)
        res = []
        
        while i < m and j < n:
            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

350 Intersection of Two Arrays II -> Binary Search

class Solution(object):
    def intersect(self, nums1, nums2):
        nums1.sort()
        nums2.sort()
        
        if len(nums1) < len(nums2):
            shortNums = nums1 ; longNums = nums2
        else:
            shortNums = nums2 ; longNums = nums1
            
        res = []
        left, right = 0, len(longNums)
        for ele in shortNums:
            index = self.binarySearch(longNums, res, left, right, ele)
            if index != -1:
                left = index + 1
                res.append(longNums[index])
        return res

    
    def binarySearch(self, longNums, res, left, right, target):
        while left + 1 < right:
            mid = (left + right) // 2
            if longNums[mid] == target:
                right = mid
            elif longNums[mid] < target:
                left = mid
            else:
                right = mid
        
        if left < len(longNums) and longNums[left] == target:
            return left
        if right < len(longNums) and longNums[right] == target:
            return right
        return -1