Finding all smaller digits for every entry in the array towards the right

Question

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

• greybeard: In the problem descriptions hyperlinked, I find numbers instead of digits. (Digits would allow to use counting.)
• greybeard: (There is no lenght.)
• greybeard: (Consider processing array elements right-to-left.)
• Jan Kuiken: @Felix, you accepted vnp's answer, probably you created a solution with vnp's hints. Could you post this solution as an answer to your own question (with of course credits to vnp) for future readers of this question?
• Felix: @JanKuiken Yes I indeed created a solution for the problem. However I think it would be very unpolite regarding the author of the question(kata) on codewars, since this is supposed to be a level 3 exercise (level 1 being the hardest and level 8 being the lowest) and therefore hard to solve without an explicit solution online. Anyone being good enough to solve a leve 3 exercise, reading my code and reading the accepted solution should be able to reproduce my solution with a bit of thinking :)

Answer 1

• Don't reinvent the wheel. Python has a bisect module; use bisect_left.

• Popping an arbitrary element from a list has a linear time complexity, which drives the total time complexity of your solution to quadratic. Unfortunately you have to reconsider an algorithm.

• The problem is very similar to counting inversions. The only difference is that you are interested not in a total amount of inversions, but in a per-element ones. This observation suggests yet another variation on a merge sort theme. I don't want to spell out the algorithm. As a hint, merge sort value, count tuples.