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

349.Intersection-of-Two-Arrays.py

# 349. Intersection of Two Arrays
# Time: O(n)
# Space: O(n)

'''
             i
[1, 1, 2, 2, 3, 5]
[2, 2, 5]
       j
'''

# 2.0 more elegant 

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        
        intersection12 = []
        i, j = 0, 0 
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j] and ( i == 0 or nums1[i] != nums1[i-1] ):
                intersection12.append(nums1[i])    
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else: // nums1[i] > nums2[j] or (nums1[i] == nums2[j] and duplicate)
                j += 1
            
        return intersection12

# 1.0 

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