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