## Problem

- 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.

## Thought Process

- unlike 349, this problem requires each element appear as it shows in original arrays
- use a dict to store number count, (which I believe is similar to map in C++)
- for num in nums1, if num exists in nums2 and
- num does not exist in count, count[num] = 1
- if num already exits in count, count[num] += 1
- also it’s important to remove the num from nums2 for each iteration to avoid double count

- return a result that has num (key) * appearance (value)

## White Board

Below is the white board:

## Code

```
class Solution:
def intersection(self, nums1, nums2):
res_d = {}
res_l = []
for num in nums1:
if num in nums2:
nums2.remove(num)
if num in res_d:
res_d[num] += 1
else:
res_d[num] = 1
for num in res_d:
res_l.extend([num] * res_d[num])
return res_l
def test_inter():
nums1 = [1, 2, 2, 1]
nums2 = [2]
# nums1 = [4,9,5,9,4]
# nums2 = [9,4,9,8,4]
inter = Solution().intersection(nums1, nums2)
print(inter)
test_inter()
```

```
[2]
```

## Complexity

- In cpython, a dictionary is implemented with a hash table, with average time complexity of O(1); a major disadvantage of hash tables is losing the order
- Time complexity is O(n), as one iteration is needed
- Space complexity is O(n), as I created both a dict and list to store results

## Optimization

If both arrays are ordered, then no need to use built in ds, create two pointers:

- if nums[i] == nums[j]
- if nums[i] in res, res[nums[i]] += 1
- if nums[i] not in res, res[nums[i]] = 1
- i += 1
- j += 1

- if nums[i] < nums[j]
- i += 1
- j stays

- if nums[i] > nums[j]
- j += 1
- i stays

```
class Solution2:
def inter_ord(self, nums1, nums2):
idx, jdx = 0, 0
res = {}
res_l = []
nums1, nums2 = sorted(nums1), sorted(nums2)
# make sure input arrays are sorted
# sorted method has a complexity of O(nlogn)
while idx < len(nums1) and jdx < len(nums2):
if nums1[idx] == nums2[jdx]:
if nums1[idx] in res:
res[nums1[idx]] += 1
else:
res[nums1[idx]] = 1
idx += 1
jdx += 1
elif nums1[idx] < nums2[jdx]:
idx += 1
else:
jdx += 1
for k in res:
res_l.extend([k] * res[k])
return res_l
def test_inter2():
# nums1 = [1, 2, 2, 1]
# nums2 = [2]
nums1 = [4,9,5,9]
nums2 = [9,4,9,8,4]
inter = Solution2().inter_ord(nums1, nums2)
print(inter)
test_inter2()
```

```
[4, 9, 9]
```

We need to sort the arrays first, in python the time complexity for sorted method is O(nlogn), space complexity is O(n) as we need additional ds to store the results.