# 350. Intersection of Two Arrays II

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