python - Counting elements in 2 arrays (GFG)

Question

I was working on a GFG question

Question:

Given two unsorted arrays arr1[] and arr2[]. They may contain duplicates. For each element in arr1[] count elements less than or equal to it in array arr2[].

Example 1:

Input:

m = 6, n = 6

arr1[] = {1,2,3,4,7,9} arr2[] = {0,1,2,1,1,4}

Output: 4 5 5 6 6 6

Explanation: Number of elements less than or equal to 1, 2, 3, 4, 7, and 9 in the second array are respectively 4,5,5,6,6,6

Example 2:

Input:

m = 5, n = 7

arr1[] = {4 8 7 5 1}

arr2[] = {4,48,3,0,1,1,5}

Output: 5 6 6 6 3

Your Task : Complete the function countEleLessThanOrEqual() that takes two array arr1[], arr2[], m, and n as input and returns an array containing the required results(the count of elements less than or equal to it in arr2 for each element in arr1 where ith output represents the count for ith element in arr1.)

Expected Time Complexity: O((m + n) * log n).

Expected Auxiliary Space: O(1).

Constraints: 1<=m,n<=10^5 1<=arr1[i],arr2[j]<=10^5

My python solution:

def countEleLessThanOrEqual(arr1,n1,arr2,n2):
    #returns the required output
    
    res=[]
    
    arr2.sort()
    
    for i in range(n1):
        search=arr1[i]
        
        count=0
        start=0
        end=n2-1
        
        while(start<=end):
            
            mid = int(start+(end-start)/2)
            
            if search==arr2[mid]:
                start=mid+1
            
            elif search>arr2[mid]:
                start=mid+1
            
            elif search<arr2[mid]:
                end=mid-1
        
        count=end+1   
        res.append(count)
        
    return res

When I submit it, it gives me TLE error even though my solution is similar to the one posted in the editorial:

Editorial solution:

# python implementation of For each element in 1st 
# array count elements less than or equal to it
# in 2nd array

# function returns the index of largest element 
# smaller than equal to 'x' in 'arr'. For duplicates
# it returns the last index of occurrence of required
# element. If no such element exits then it returns -1
def bin_search(arr, n, x):
    
l = 0
h = n - 1
while(l <= h):
    mid = int((l + h) / 2)
    # if 'x' is greater than or equal to arr[mid], 
    # then search in arr[mid + 1...h]
    if(arr[mid] <= x):
    l = mid + 1;
    else:
    # else search in arr[l...mid-1]
    h = mid - 1
# required index
return h

# function to count for each element in 1st array,
# elements less than or equal to it in 2nd array
def countElements(arr1, arr2, m, n):
# sort the 2nd array
arr2.sort()

# for each element in first array
for i in range(m):
    # last index of largest element 
    # smaller than or equal to x
    index = bin_search(arr2, n, arr1[i])
    # required count for the element arr1[i]
    print(index + 1)

# driver program to test above function
arr1 = [1, 2, 3, 4, 7, 9]
arr2 = [0, 1, 2, 1, 1, 4]
m = len(arr1)
n = len(arr2)
countElements(arr1, arr2, m, n)

# This code is contributed by Aditi Sharma

question from:https://stackoverflow.com/questions/66065988/counting-elements-in-2-arrays-gfg

Answer 1

You could use a binary search on the second array after sorting it in place:

from bisect import bisect_right

def lowerCount(arr1,arr2):
    arr2.sort()
    return [bisect_right(arr2,v) for v in arr1]


print(*lowerCount([1,2,3,4,7,9],[0,1,2,1,1,4]))      # 4 5 5 6 6 6
print(*lowerCount([4, 8, 7, 5, 1],[4,48,3,0,1,1,5])) # 5 6 6 6 3

Sorting arr2 is O(N log N), and binary searches will take O(M log N) for a total of O( (N+M) log N ).

If you can't use libraries, you could always write your own bisect_right function:

def bisect_right(A,x):
    lo,hi  = 0,len(A)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if A[mid] <= x: lo = mid+1
        else:           hi = mid-1
    return hi+1