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

# 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, and 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. So the time complexity for intersection is O(min(len(nums1), len(nums2))), but space complexity is O(n).