5
\$\begingroup\$

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?

\$\endgroup\$

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.