## Description

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

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

**Example 1:**

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

**Example 2:**

Input:nums1 = [4,9,5], nums2 = [9,4,9,8,4]Output:[4,9]

**Note:**

- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.

**Follow up:**

- What if the given array is already sorted? How would you optimize your algorithm?
- What if
*nums1*‘s size is small compared to*nums2*‘s size? Which algorithm is better? - What if elements of
*nums2*are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

## Explanation

Use a temp array to store the element in rotating order

## Python Solution

```
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
counter = {}
for num in nums1:
if num in counter:
counter[num] += 1
else:
counter[num] = 1
result = []
for num in nums2:
if num in counter and counter[num] != 0:
result.append(num)
counter[num] -= 1
return result
```

- Time complexity: O(
*n*+*m*), where n and m are the lengths of the arrays. We iterate through the first, and then through the second array; insert and lookup operations in the hash map take a constant time. - Space complexity: O(min(
*n*,*m*)). We use a hash map to store numbers (and their counts) from the smaller array.