The array contains digits and it is unsorted. Its length could be as big as 120000. I need to count the smaller numbers to the right of each digit.
This is a coding challenge on Codewars which requires a specific code efficency to be completed (Solve X amount in Y time). https://www.codewars.com/kata/56a1c63f3bc6827e13000006/train/python
Example:
100, 10, 10, 10, 10]should return 4, 0, 0, 0, 0
1, 2, 3 should return 0, 0, 0
1, 2, 0 should return 1, 1, 0
1, 2, 1 should return 0, 1, 0
My current approach is to sort the array and then do a binary search inside that array for the current number. Afterwards I skip over the possible duplicates of this number and search for the next smaller number and return the amount of all leftover entities. I then remove the just used number out of the sorted array.
My question is mostly about using a fast approach to this problem, since the time needed with my program takes too long.
def smaller(arr):
sorted_arr = sorted(arr)
lenght = len(arr)
for i in range(lenght):
pos = binary_search(sorted_arr, arr[i])
while sorted_arr[pos] == sorted_arr[pos-1] and pos-1>=0:
pos -= 1
arr[i] = pos
sorted_arr.pop(pos)
return arr
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid-1
else:
return mid
return -1
lenght.) \$\endgroup\$