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
            dict_count[num1] += 1

    inter_arr = []

    for num2 in nums2:
        if num2 in dict_count and dict_count[num2] > 0:
            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
            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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.