349. Intersection of Two Arrays

Easy

Problem:

Find the intersection of two arrays.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

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

Solution:

Binary Search

If you search one array in order and sort the other to search for values using binary search, the search efficiency can be significantly improved. The time complexity would be $O(nlogn)$.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result: Set = set()
        nums2.sort()
        for n1 in nums1:
            i2 = bisect.bisect_left(nums2, n1)
            if len(nums2) > 0 and len(nums2) > i2 and n1 == nums2[i2]:
                result.add(n1)
        return result

Two Pointers

Both arrays can be sorted and then solved using two pointers. It's similar to the process of comparing the final results during merge sort, but the difference is that we determine matching values. The time complexity is $O(nlogn)$.

The pointer of the smaller value array moves one step forward. The process ends when the pointer of one side reaches the end.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result: Set = set()
        nums1.sort()
        nums2.sort()
        i = j = 0

        while i < len(nums1) and j < len(nums2):
            if nums1[i] > nums2[j]:
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                result.add(nums1[i])
                i += 1
                j += 1
        
        return result

Other algorithms:

Brute Force

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result: Set = set()
        for n1 in nums1:
            for n2 in nums2:
                if n1 == n2:
                    result.add(n1)
        return result

Hash Table

import collections
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        dict_nums1 = collections.Counter(nums1)
        dict_nums2 = collections.Counter(nums2)

        result = []
        for (key, value) in dict_nums1.items():
            if dict_nums1[key] and dict_nums2[key]:
                result.append(key)
        return result