trjhtr

I am currently working on an algorithm, which involves finding the intersection of two lists. That is, given the following inputs [1,2,2,1],[2,2] the result would be [2,2].

I have implemented it in two ways which hopefully should be easy to understand

Method 1

def intersect(nums1, nums2):
 dict_count = 
 for num1 in nums1:
 if num1 not in dict_count:
 dict_count[num1] = 1
 else:
 dict_count[num1] += 1

 inter_arr = 

 for num2 in nums2:
 if num2 in dict_count and dict_count[num2] > 0:
 inter_arr.append(num2)
 dict_count[num2] -= 1

 return inter_arr

Method 2

def intersect_v2(nums1, nums2):
 arr_one = sorted(nums1)
 arr_two = sorted(nums2)

 p1, p2 = 0, 0
 inter_arr = 

 while p1 < len(arr_one) and p2 < len(arr_two):
 if arr_one[p1] < arr_two[p2]:
 p1 += 1
 elif arr_one[p1] > arr_two[p2]:
 p2 += 1
 else:
 inter_arr.append(arr_one[p1])
 p1 += 1
 p2 += 1

 return inter_arr

I have two questions about time complexity:

• What if nums1's size is small compared to nums2's size? Which algorithm is better? (The original algorithm problem is from Leetcode and this is a follow up question to the problem)

It feels like the pointer method always win, but I can't articulate why.

• If the inputs always came in sorted, which algorithm would be more efficient with respect to time and space? (This would mean that first two lines to intersect_v2 would not be needed)

From my understanding intersect would be O(M+N) since you would have to iterate through the two arrays not matter what. The second one is a bit confusing since it feels like the it would be O(Z) where Z is less than Max(M,N) and greater than Min(M,N), is that about right?