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

user_9131718 0
Viewed 50

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)

algorithm
2 Answers

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)
user_93507200

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))

user_86770710
Related