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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/array/349intersection-of-two-arrays.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.