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