# Two Python solutions

• First solution: not sure about the time complexity, anyone knows the complexity of dict.has_key?

Or we can choose the shorter array to do the search, which can save some time. This also answers the follow-up question #2.

Second solution, sort(). 52ms too. Of course, if the array is pre sorted, second solution saves a lot of time. This answers the follow-up question #1.

About the follow-up questions #3, solution 1 works well. We can save nums1 first, and check each element in nums2.

solution 1: using dict 52ms

``````    def intersect(self, nums1, nums2):
import collections

dict1 = dict(collections.Counter(nums1))
res = []

for i in nums2:
if dict1.has_key(i):
if dict1[i] > 0:
dict1[i] -= 1
res.append(i)

return res
``````

solution 2: sort() 52ms

``````    def intersect(self, nums1, nums2):

nums1.sort()
nums2.sort()

res = []

i, j = 0, 0

while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
res.append(nums1[i])
i, j = i + 1, j + 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1

return res
``````

• Good point about using the shorter array to do the search. I went back after reading that and adjusted my code and it went from `72ms` to `45ms`!

One question though, is there a particular reason why you import inside of the function VS at the top of the file? That idea is new to me.

Here's my solution to this problem:

``````from collections import Counter

class Solution(object):
def intersect(self, nums1, nums2):
cnt_1, cnt_2 = sorted([Counter(nums1), Counter(nums2)])
result = []
for k, v in cnt_1.iteritems():
current = cnt_2.get(k)
if current is not None:
result.extend([k] * min(current, v))
return result

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.