3
\$\begingroup\$

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

1 Answer 1

3
\$\begingroup\$
  • 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.