# 349. Intersection of Two Arrays

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