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

Think of a pathological case where nums1 = [1_000_000] and nums2 = list(range(100_000)). The pointer approach would increment p2 100_000 times trying to find an element equal to or greater than 1_000_000.

What are some ways you can mitigate that?

Taking advantage of the fact that nums1 and nums2 would be sorted, you could get the min and max of each list in O(1) and use those as additional conditions to break out of the while loop earlier.

Another thing to look into is bisect.bisect_left, which is python's own implementation of binary search. Given that you're assuming sorted input, binary search could speed things up as follows:

while p1 < len(nums1) and p2 < len(nums2):
    if nums1[p1] < nums2[p2]:
        # advance p1 to an index s.t. nums1[p1] >= nums2[p2]
        p1 = bisect.bisect_left(nums1, nums2[p2])
    elif nums1[p1] > nums2[p2]:
        # advance p2 to an index s.t. nums2[p2] >= nums1[p1]
        p2 = bisect.bisect_left(nums2, nums1[p1])
    else:
        inter_arr.append(arr_one[p1])
        p1 += 1
        p2 += 1

Blockquote

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

Granted, in many cases, the pointer method might be faster because it might break out of the while after exhausting the elements of the smaller list without having to consider the vast majority of the elements of the larger list.

However, think of a pathological worst case where max(nums1) > max(nums2) such as nums1 = [1_000_000] and nums2 = list(range(100_000)). The pointer approach as shown would have to examine all 100_000 elements of nums2.

What are some ways you can mitigate this?

Taking advantage of the fact that nums1 and nums2 are sorted, you can get the min and max of each list in O(1) and use those values as additional conditions to break out of the while loop earlier.

Given that the input is sorted, binary search might speed things up considerably. bisect.bisect_left is python's own implementation of binary search. Given that sorted input, binary search would allow you to potentially skip over larges swaths of the input as follows:

while p1 < len(nums1) and p2 < len(nums2):
    if nums1[p1] < nums2[p2]:
        # advance p1 to an index s.t. nums1[p1] >= nums2[p2]
        p1 = bisect.bisect_left(nums1, nums2[p2])
    elif nums1[p1] > nums2[p2]:
        # advance p2 to an index s.t. nums2[p2] >= nums1[p1]
        p2 = bisect.bisect_left(nums2, nums1[p1])
    else:
        inter_arr.append(arr_one[p1])
        p1 += 1
        p2 += 1

P.S.: bisect_left has two optional keyword arguments, lo and hi which might be useful here as well.