2018-10-26 Intersection of Two Arrays [E]

547. Intersection of Two Arrays
     Given two arrays, write a function to compute their intersection.

LC: 349

Example
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Challenge
Can you implement it in three different algorithms?

Notice
Each element in the result must be unique.
The result can be in any order.

The key of this problem is its follow-up questions. That is how to solve this in three different ways (different time and space complexity).

1. Hash Set: Time: O(n + m) Space: O(min(n, m))

class Solution:
    """
    @param nums1: an integer array
    @param nums2: an integer array
    @return: an integer array
    """
    def intersection(self, nums1, nums2):
        if len(nums2) < len(nums1):
            nums1, nums2 = nums2, nums1
            
        unique = set(nums1)
        result = []
        for n in nums2:
            if n in unique:
                unique.discard(n)
                result.append(n)
        return result

Notes:

• Need to remember how to remove one element from set, set.discard(elem).

2. Merge Sorted Arrays - Only Merge Duplicates: Time O(nlogn + mlogm) Space O(1)

    def intersection(self, nums1, nums2):
        nums1.sort()
        nums2.sort()
        result = []
        
        p1, p2 = 0, 0
        
        while (p1 < len(nums1)) and (p2 < len(nums2)):
            if nums1[p1] == nums2[p2]:
                result.append(nums1[p1])
                p1 += 1
                p2 += 1
                
                while (p1 < len(nums1) and nums1[p1] == nums1[p1 - 1]):
                    p1 += 1
                while (p2 < len(nums2) and nums2[p2] == nums2[p2 - 2]):
                    p2 += 1
                
            elif nums1[p1] < nums2[p2]:
                p1 += 1
            else:
                p2 += 1
            
        return result

-Really need to be careful about spelling of result.

3. Binary Search: Time O((n+m)log(min(m,n))) Space O(1)

(mlogm for sorting and nlogn for looping)

    def intersection(self, nums1, nums2):
        if not nums1 or not nums2:
            return []
            
        if len(nums2) < len(nums1):
            nums1, nums2 = nums2, nums1
        
        results = set()
        nums1.sort()
        for n in nums2:
            if self.bs(nums1, n):
                results.add(n)
        
        return list(results)
                
        
    def bs(self, nums, target):
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (end - start) // 2 + start
            if nums[mid] < target:
                start = mid
            elif nums[mid] > target:
                end = mid
            else:
                return True
        
        if nums[start] == target or nums[end] == target:
            return True
        else:
            return False
    

Notes:

• Something interesting happened here. I wanted to use

result = self.bs(nums, target)
if result: 
    results.add(result)

However, element can be integer zero and should be put into results. Therefore, always be careful if I want to use an integer in if-statement!

-Always consider edge cases. If you want to do binary search, the array can never be empty. So always check.

4. Shortcut - take advantage of Python. Time O(m + n) Space O(m + n)

(more space needed than Approach #1)

    def intersection(self, nums1, nums2):
        return list(set(nums1) & set(nums2))

Notes:

• set & set is just the shortcut to find intersection.

Follow-up: save duplicates if duplicates exist

• Approach #1: use hashmap as counters instead of set.
• Approach #2: Small modifications.
• Approach #3: OK, but need extra space. [1, 2, 1, 2] => [1(2), 2(2)], then do binary search.

TO-DO

Intersection of Arrays - when merging k arrays, check if one elements occur k times.