List all numbers smaller in sorted array in O(n)-CodePudding

I have two sorted arrays, I would like to find out how to list the count of the numbers in array 1 that are bigger than the numbers in array 2.

For example, [1,4,6,8] and [4,6,7,9] would return 4 as 6 is bigger than 4 and 8 is bigger than 4,6,7. Currently the best way I can do this is in O(n^2) by looping over each array, however I'm not sure how to do it in O(n)

CodePudding user response：

Using two pointers should suffice, since the arrays are sorted. This logic is similar to the merge step of Merge Sort, we're just keeping a track of the number of elements here.
Time Complexity: O(N)

a = [1,4,6,8]
b = [4,6,7,9]
l,r = 0,0
n,m = len(a), len(b)
ans = 0
while l<n and r<m:
    if a[l]>b[r]:
        ans  = n-l
        r  = 1
    else:
        l  = 1
print(ans)

CodePudding user response：

You can use the two-pointer technique, we can keep two pointers - p1 in the first list and p2 in the second list. We keep on incrementing p1 till the number at p1 in list1 is smaller than the number at p2 in list2. Otherwise, just increment the count by number of elements we have to the right of p1

def smaller_count(list1, list2):
    l1, l2, ans = len(list1), len(list2), 0
    # pointers in list1 and list2
    p1, p2 = 0, 0
    while p1 < l1 and p2 < l2:
        if list1[p1] > list2[p2]:
            ans  = l1 - p1
            p2  = 1
        else:
            p1  = 1
    return ans

>>> smaller_count([1,4,6,8], [4,6,7,9])
4
>>> smaller_count([1,4,6,8], [0])
4
>>> smaller_count([1,4,6,8], [10])
0
>>> smaller_count([1,4,6,8], [0, 1, 2, 3])
13

Since we are iterating over the two lists only once, the complexity would be O(len(list1) len(list2))