# Intersection of two lists in Python

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?