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