fastest way to find number of smaller elements to the right of an array

Question

In Daily Coding Problem, Miller&Wu have the following problem : Given an array of integers, return a new array where each element in the new array is number of smaller elements to the right of that element in the original input array.

Their suggested solution is (in python):

import bisect

def smaller_counts(lst):
   result = []
   seen = []
   for num in reversed(lst):
      i = bisect.bisect_left(seen, num)
      resul.append(i)
      bisect.insort(seen, num)
    return list(reversed(result))

While the algorithm is correct, the authors then claim that it takes O(n log(n)), which seems wrong to me:I'd expect the call to insort to be a O(num), since we're inserting in an array and we need to move all the elements after num to the right of that array. That's also confirmed by python doc.

As a result, I think it's a total cost of O(n^2).

Am I missing something, or did the authors make a mistake here (probably assuming that the insort would have the same log(num) cost as the bisect_left) ?

I also thought of posting this on code golf, but wasn't sure it belonged there.

Answer 1

Your reasoning seems correct. Making n iterations over an O(n) operation means O(n²) total complexity in general. Whether the insertion actually has O(n) time complexity depends on the data distribution. For example, if we were to insert elements in ascending order (so that new elements are only appended, without shifting existing values) then it could be as cheap as O(1). However, this scenario does not make it possible to make any assumptions about the data distribution.

Note that an O(n log n) solution is possible if seen is an ordered set data structure with O(log n) insertion, such as a balanced binary tree. Python has no suitable data structure in the standard library. The heapq module is similar but cannot provide the necessary operations here. A possible manual implementation might look like this:

from dataclasses import dataclass
from typing import Optional, Tuple

def smaller_counts(lst: list[int]) -> list[int]:
    result = []
    seen = None
    for num in reversed(lst):
        location, seen = treeset_insert_and_get_location(seen, num)
        result.append(location)
    return list(reversed(result))

@dataclass
class Node:
    value: int
    size: int
    left: 'Optional[Node]' = None
    right: 'Optional[Node]' = None

    @property
    def left_size(self) -> int:
        if self.left is not None:
            return self.left.size
        return 0

    @property
    def right_size(self) -> int:
        if self.right is not None:
            return self.right.size
        return 0


def treeset_insert_and_get_location(
        tree: Optional[Node], value: int,
) -> Tuple[int, Node]:
    if tree is None:
        return 0, Node(value=value, size=1)

    if value < tree.value:
        location, tree.left = treeset_insert_and_get_location(
            tree.left, value)
        tree.size += 1
        return location, tree

    if value > tree.value:
        location, tree.right = treeset_insert_and_get_location(
            tree.right, value)
        tree.size += 1
        return tree.size - tree.right_size + location, tree

    assert tree.value == value
    tree.size += 1
    return tree.left_size, tree

^{full code incl. tests}

In practice, the presented solution in the question is still going to be reasonably efficient at smaller input sizes. The O(n) insertion is the kind of operation that modern computers are fairly good at. I'd expect that the presented solution, or even a naive O(n²) solution, would outperform any tree-based data structure until about a few hundred or a few thousand elements.

Answer 2

An obvious solution is sorting a copy of the original array while keeping track of the location of each item in the original array, and then all the information to calculate the result is readily available. Can be done in O(n log n).

Experimentally you can use their algorithm for an array with 1,000, 10,000, 100,000 and a million random items. Execution time should grow by a factor less than 15 each time if it is n log n, and a factor 100 if quadratic.