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

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

• In the problem descriptions hyperlinked, I find numbers instead of digits. (Digits would allow to use counting.) Jul 17 at 4:25
• (There is no lenght.) Jul 17 at 4:27
• (Consider processing array elements right-to-left.) Jul 17 at 4:30
• @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? Jul 18 at 17:02
• @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 :) Jul 19 at 11:17

• Don't reinvent the wheel. Python has a bisect module; use bisect_left.
• 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.