## Problem

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

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

Note:

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

## Thought Process

- use a dict to store number count
- for num in nums1, if num exists in nums2 and num does not exist in count, count[num] = 1
- for num in nums2, if num exists in nums1 and num does not exist in count, count[num] = 1
- return only count keys

## White Board

Below is the white board, and note the 2nd loop is not necessary

## Code

```
class Solution:
def intersection(self, nums1, nums2):
res = {}
for num in nums1:
if num in nums2 and num not in res:
res[num] = 1
return list(res.keys())
def test_inter():
# nums1 = [1, 2, 2, 1]
# nums2 = [2, 2]
nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
inter = Solution().intersection(nums1, nums2)
print(inter)
test_inter()
```

```
[4, 9]
```

## Complexity

- Time complexity is O(n * m), as one iteration is needed, within the loop check in takes O(m)
- Space complexity is O(k), k is the size of intersection, as I created a dict(HashTable)

## Optimization

Can simplify it with python built in set ds

```
class Solution2:
def intersection2(self, nums1, nums2):
set1, set2 = set(nums1), set(nums2)
return list(set1 & set2)
def test_inter2():
# nums1 = [1, 2, 2, 1]
# nums2 = [2, 2]
nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
inter = Solution2().intersection2(nums1, nums2)
print(inter)
test_inter2()
```

```
[9, 4]
```

In cpython, set is implemented with hash tables. The time complexity for dict intersection is O(min(len(nums1), len(nums2))), but space complexity is O(n).