# 349. Intersection of Two Arrays

## 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)$$.

```python
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
```

### <mark style="color:purple;">Two Pointers</mark>

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.

```python
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
```

<details>

<summary>Other algorithms:</summary>

### Brute Force

```python
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

```python
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
```

</details>
