# 349\_Intersection of Two Arrays

\[Easy]\[Array, Two Pointers, Binary Search, Hash Table, Sort]

Given two arrays, write a function to compute their intersection.

**Note:**

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

**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]
```

## Solution 1: Sort + Binary Search

**Idea**:

* Sort the two arrays first.
* Loop over each element in one array, use binary search to find if that element exist in the other array.
* We can choose smaller length array for the loop, such that the time complexity will be smaller.
* This approach has advantage if one array is much smaller in size than the other one.

**Time Complexity**: $$O(m \log{n})$$ or $$O(n\log{m})$$

**Space Complexity**: $$O(1)$$

```python
def intersect(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    # sort two arrays
    nums1.sort()
    nums2.sort()

    def is_present(a):
        # get the location to insert a into nums2
        # on the left of any existing entries
        import bisect
        i = bisect.bisect_left(nums2, a)
        return i < len(nums2) and nums2[i] == a

    return [
        a for i, a in enumerate(nums1) 
        if is_present(a) and (i == 0 or a != nums1[i-1])
    ]
```

## Solution 2: Sort + Two Pointers

**Idea**:

* First sort the two arrays.
* Simultaneously advance through the two arrays in increasing order. At each iteration:
  * If the two elements differ, eliminate the small one.
  * If they are the same, append to output and advance both.&#x20;
* If the length of two arrays are similar, this solution has advantage.

**Time Complexity**: $$O(m \log{m} + n \log{n} + m + n)$$

**Space Complexity**: $$O(1)$$

```python
def intersect(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    # sort two arrays
    nums1.sort()
    nums2.sort()

    # two pointers
    p1, p2 = 0, 0
    output = []
    while p1 < len(nums1) and p2 < len(nums2):
        if nums1[p1] > nums2[p2]:
            p2 += 1
        elif nums1[p1] < nums2[p2]:
            p1 += 1
        else:
            if len(output) == 0 or nums1[i] != output[-1]:
                 output.append(nums1[i]) 
            p1 += 1
            p2 += 1
    return output
```

## Solution 3: Dictionary

**Idea**:

* Count frequency of each number in nums1, store in a dictionary.
* Loop for each element in nums2, check if it has a pair in the dictionary. If yes, append the element, and decrease the corresponding frequency by 1.

**Time Complexity**: $$O(m+n)$$

**Space Complexity**: $$O(m)$$ or $$O(n)$$, can choose the smaller one.

```python
def intersect(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    counts = {}
    output = []
    # count frequency of each number in nums1
    for num in nums1:
        counts[num] = 1 
    # check if each number in nums2 has a pair
    for num in nums2:
        if num in counts and counts[num] > 0:
            output.append(num)
            counts[num] -= 1
    return output
```