7
\$\begingroup\$

I have to solve the task which finds the count of values, are smaller than the current one, located to the right. Here is the example:

# We have list
list = [5, 4, 3, 2, 1]

First answer is 4, because we have 4 values to the right are smaller than the first one is 5.
Second answer is 3, because we have 3 values are smaller to the right than the current one is 4 and etc.
The final answer is the list of counts. For my example the final answer is:

[4, 3, 2, 1, 0]

Other examples:

[1, 2, 0] --> [1, 1, 0]
[1, 2, 3] --> [0, 0, 0]
[1, 2, 1] --> [0, 1, 0]
[1, 1, -1, 0, 0] --> [3, 3, 0, 0, 0]
[5, 4, 7, 9, 2, 4, 4, 5, 6] --> [4, 1, 5, 5, 0, 0, 0, 0, 0]

Link of problem

Time is limited - 12000ms

So I found the solution of this task:

def smaller(arr):
    ans = []
    count = 0

    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if arr[j] < arr[i]:
                count += 1
        ans.append(count)
        count = 0

    return ans

But It works too slow with large inputs, so I decided to optimize It. I am sorting all values to the right of the current and If I meet the value is not smaller, then I break from the loop. Here is what I did:

def smaller(arr):
    ans = []
    count = 0
    last_ind = len(arr)

    for i in range(len(arr)):
        sorted_ans = arr.copy()
        sorted_ans[i + 1:last_ind] = sorted(arr[i + 1:last_ind])

        for j in range(i + 1, len(arr)):
            if sorted_ans[j] < arr[i]:
                count += 1
            else:
                break

        ans.append(count)
        count = 0

    return ans

But anyways It works slowly. Could you tell me, how can I optimize my code better? Thx a lot!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Mast
    Commented Aug 26, 2022 at 15:36
  • \$\begingroup\$ Consider waiting a day and posting a new question with your revised code. \$\endgroup\$
    – Mast
    Commented Aug 26, 2022 at 15:36

3 Answers 3

4
\$\begingroup\$

You show example problem instances and answers:
A head-start for a test!

Imagine coming across your second smaller() a decade from now:
Can you readily tell what it is to return? What its parameter can be?

Don't write, never commit/publish undocumented code.
Python got it right specifying docstrings such that it is easy to copy them with the code, and tedious to copy the code without them.

The first take you present is quite clear.
Nit: count isn't used outside the outer loop: initialise it once at its top.
You use indexing quite a lot - current = arr[i] would cut such access almost in half.
In Python, use of its iteration facilities isn't just pythonic, but faster more often than not:

def count_smaller_to_the_right(sequence):
    """ Return for each element of sequence 
        the count of smaller elements to its right.
    """
    counts = []
    
    for i, current in enumerate(sequence):
        count = 0
        for right in sequence[i+1:]:
            if right < current:
                count += 1
        counts.append(count)
    
    return counts


smaller = count_smaller_to_the_right  # For compatibility.

Contemporary wisdom would include type hints.
There are functional variants of getting the count of elements for which a predicate is true including sum and filter -
code the way you think about a solution.


For the second take and the insertion sort angle, see AJNeufeld's answer.

So, what approaches do we know to efficiently find the position of a value/element in a "dynamic" collection of values?
Check out order statistic data structures.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your detailed response! I named variables in my code like this because of the task on site. I have uploaded the link on this task in codewars, so If i rename the name of function or the argument it takes, then It gives me an exception that the tests have not found the function it was named before. Otherwise, It works not fast enough for limited time, as I mentioned in my question. So, please, If you would like to try to solve It again, check the link I`ve uploaded in question. Thx a lot! \$\endgroup\$
    – rockzxm
    Commented Aug 26, 2022 at 15:20
3
\$\begingroup\$

Big O

I don't think you've optimized your algorithm; I think you've deoptimized it!

The original algorithm is approximately this:

    for i in range(len(arr)):             # O(N)
        for j in range(i, len(arr)):         # O(N)
            ...

For an N element array, this looks like a nice, simple \$O(N^2)\$ algorithm.

Your "optimized" algorithm looks approximately like this:

    for i in range(len(arr)):             # O(N)
        copy                                 # O(N) 
        sort                                 # O(N log N)
        for j in range(i + 1, len(arr)):     # O(N)
           ...

For an N element array, you've got an \$O(N \log N)\$ operation inside a length N loop, making the whole process \$O(N^2 \log N)\$. Ooops.

Array Slicing

You don't need last_ind = len(arr). The only place you use it is in the slicing ...

        sorted_ans[i + 1:last_ind] = sorted(arr[i + 1:last_ind])

... but since it is the index of the end of the arrays, it can simply be omitted:

        sorted_ans[i + 1:] = sorted(arr[i + 1:])

Unused array elements

Again, consider these statements:

        sorted_ans = arr.copy()
        sorted_ans[i + 1:last_ind] = sorted(arr[i + 1:last_ind])

        for j in range(i + 1, len(arr)):
            ... sorted_ans[j] ...
            ...

The loop is only going over the elements from i + 1 on to the end of the array. These elements are replaced in the copy of arr. Elements sorted_ans[0] to sorted_ans[i] are never used. So why are we copying them from arr? The following code would be equivalent, but more efficient:

        threshold = arr[i]

        sorted_tail = sorted(arr[i + 1:])
        for element in sorted_tail:
            if element < threshold:
                count += 1
            else:
                break

Two important points:

  1. We're now using for element in sorted_tail to loop over the elements of the container directly, not the indices, so we've eliminated the inefficient sorted_ans[j] indexing operation.
  2. We're also caching the arr[i] value in threshold to also eliminate that repeated inefficient indexing operation as well.

Optimizing this further, we're still left with

def smaller(arr):
    ans = []

    for i, threshold in enumerate(arr, 1): # O(N)
        count = 0
        for element in sorted(arr[i:]):       # O(N log N)
            if element < threshold:
                count += 1
            else:
                break

        ans.append(count)

    return ans

so we still have an \$O(N \log N)\$ sort inside a loop of length N, so we still have an \$O(N^2 \log N)\$ algorithm.

We really don't want to sort inside the loop!

Sorting ... for the win?

Many coding challenges are solved quicker by sorting. This one is no exception, but we don't want to sort the array over and over inside the loop. We want to reuse the already-sorted-tail on the next iteration, to reduce the time it takes to create the next sort.

Consider the list: [50, 10, 30, 40, 20]

Let's work backwards.

The tail is initially []. The first element to consider is the 20. How many elements in the tail are smaller than it? 0. Ok, so our result initially is [0] Let's put the element into our tail as well: [20].

The next element is a 40. How many elements in the tail are smaller than it? 1. Where does it go in the tail? At position 1. (Is that a coincidence?) Our result (reading backwards) is now [0, 1], and our tail is [20, 40].

The next element is a 30. How many elements in the tail are smaller than it? Again, 1. Where does it go in the tail? Again, at position 1. (Doesn't seem like a coincidence.) Our result (reading backwards) is now [0, 1, 1], and our tail is [20, 30, 40].

The next element is a 10. How many elements in the tail are smaller than it? 0. Where does it go in the tail? Position 0. Our result (reading backwards) is now [0, 1, 1, 0], and our tail is [10, 20, 30, 40].

The next element is a 50. How many elements in the tail are smaller than it? 4. Where does it go in the tail? Position 4. Our result (reading backwards) is now [0, 1, 1, 0, 4], and our tail is [10, 20, 30, 40, 50].

Reverse the result, and we get [4, 0, 1, 1, 0], as required by the problem.

It looks like we have a simple insertion sort, where the desired result is just the list of insertion indices (reversed)!

  • Initialize a result list to []
  • Initialize a tail to []
  • Traverse elements in the input list in reverse order
    • Determine the position in the tail where the element must be inserted.
    • Append the index to the result list
    • Insert the element at the required index
  • Reverse the result list

So, how do we determine the position in the tail, a sorted list, where the element must be inserted? bisect, of course! Whether you want bisect.bisect_left(...) or bisect.bisect_right(...) for the proper handling of equal values is left to student.

Since insertion sorts are well known, we can look up the time complexity: \$O(N^2)\$.

Wait, wasn't that the time complexity of the first implementation? Well, perhaps the constant factors are smaller.

\$\endgroup\$
5
  • 4
    \$\begingroup\$ Sorry if I sound harsh - but you must see that it is just yet another twist of the inversion counting problem, and that there is an \$O(n\log{n})\$ solution. \$\endgroup\$
    – vnp
    Commented Aug 26, 2022 at 6:05
  • \$\begingroup\$ Thank you for your detailed response! I have uploaded the link on this task in codewars. Otherwise, It works not fast enough for limited time, as I mentioned in my question. So, please, If you would like to try to solve It again, check the link I`ve uploaded in question. Thx a lot! \$\endgroup\$
    – rockzxm
    Commented Aug 26, 2022 at 15:24
  • \$\begingroup\$ @vnp Yup, I recognize that now, in the light of day. Midnight last night, I'd forgotten the complexity of insertion sort, and started down that garden path ... and checked just before posting, realized my mistake, and made a few tweaks to the answer before posting it. Don't worry, you don't sound harsh; I appreciate that you believed I should have seen the correct approach. 8^D \$\endgroup\$
    – AJNeufeld
    Commented Aug 26, 2022 at 22:00
  • 2
    \$\begingroup\$ @rockzxm "So, please, If you would like to try to solve It again..." You're missing the point of CodeWars. You are supposed to determine the required algorithm, and write the code to solve the problem. Note that even in my answer, I had an section of my approach "left to student" so you could work through the problem yourself and learn from it. On Code Review, we'll review working code, point out areas where things code be more efficient, and help you write better code ... but when you are trying to solve a programming challenge, you'll often find our answers leave work for you. \$\endgroup\$
    – AJNeufeld
    Commented Aug 26, 2022 at 22:10
  • \$\begingroup\$ @AJNeufeld I am just not an intermediate in english, so the meaning of my phrase if you would like to try to solve it again was not as literally as you said. Just if you have any ideas about the optimizing the code, or the solution with another optimized algorithm, you can write it again after you have checked the source of the task ^^ \$\endgroup\$
    – rockzxm
    Commented Aug 26, 2022 at 23:18
1
\$\begingroup\$

Assuming that the lists always contain small integers, it is possible to sort in O(n) rather than O(n log n). This is called “histogram sort”. In short, you count how many of each integer is in the array, by computing the histogram, then you write out those integers in order.

The interesting thing about the histogram is that you can update it cheaply. Add a number to your list? Increment one histogram bin. Remove a number from the list? Decrement one histogram bin. So in the current problem, we don’t need to repeatedly sort a shrinking list, we just need to repeatedly update the histogram.

Also, we can determine how many elements are smaller than k by summing up the histogram bins from 0 to k (excluded). This is an operation of O(m), where m is the range of the integers in the list.

So, it should be possible to solve the problem in O(nm):

  1. Create a histogram of the input array.
  2. For each element k in the input array:
    1. Decrement bin k in the histogram.
    2. Output sum(histogram[:k])

The above is very efficient as long as integers are small wrt the array size, m < n. If values are much larger, the histogram will be sparsely populated, making the summation operation relatively expensive. If the input consists of floating-point values, the histogram is not viable at all. In both of these cases, the order-statistic tree mentioned by greybeard would be needed. This will make the code significantly more complex, but would provide O(log n) updates and O(log n) counting, making the overall problem O(n log n). I recently wrote a blog post about my experiences with this data structure: https://www.crisluengo.net/archives/1138/

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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