1
\$\begingroup\$

Input: an array of length \$n\$ containing integers in the range \$0\$ to \$2n\$.

For each integer \$x\$ in the array, compute the number of integers that occur before \$x\$ that are no larger than \$x\$.

As an example, if the array is

[3, 0, 1, 4, 3, 6]

the output should be equivalent to:

3: 0
0: 0
1: 1
4: 3
3: 3
6: 5

How quickly can you compute this as a function of \$n\$?

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Under what model is the complexity calculated? Is it the word RAM model? \$\endgroup\$ Sep 28, 2023 at 18:43
  • \$\begingroup\$ I think you need a bit more detail for "How quickly can you compute this as a function of đť‘›?". It seems almost trivial to make an algorithm that runs in O(n), and impossible to be faster (since the output has length n and so must be O(n) to simply write the output... \$\endgroup\$ Sep 28, 2023 at 18:44
  • \$\begingroup\$ @DominicvanEssen I don't believe there's a known \$O(n)\$ algorithm, although \$O(n\log n)\$ is known and fairly simple \$\endgroup\$ Sep 28, 2023 at 18:45
  • 2
    \$\begingroup\$ @Simd - The method for your previous challenge was O(n) because the size of the integers was bounded at 14. Here it's linked to n. But, even so, it'll be difficult to discriminate between different O(n x log(n)) approaches without an additional tie-breaking criterion... \$\endgroup\$ Sep 28, 2023 at 18:54
  • 4
    \$\begingroup\$ This paper describes an O(n sqrt log n) algorithm. \$\endgroup\$ Sep 29, 2023 at 3:24

2 Answers 2

10
\$\begingroup\$

Python, \$O(n \frac{\log n}{\log \log n})\$

Uses the approach from the paper "Optimal Algorithms for List Indexing and Subset Rank".

import math


def partial_sums(arr):
    for i in range(1, len(arr)):
        arr[i] += arr[i - 1]
    return [0] + arr


class ShortSum:
    cache = None

    def __init__(self, size):
        self.sz = size
        self.logsz = int(math.log2(size)) + 1
        if ShortSum.cache is None:
            ShortSum.cache = [partial_sums([(v >> (i * self.logsz)) & ((1 << self.logsz) - 1) for i in range(self.sz)])
                              for v in range(1 << (self.sz * self.logsz))]
        self.cnt = 0
        self.b = [0] * size
        self.c = 0

    def prefix(self, v):
        return self.b[v] + ShortSum.cache[self.c][v]

    def inc(self, v):
        self.c += 1 << (v * self.logsz)
        self.cnt += 1
        if self.cnt == self.sz:
            self.cnt = 0
            for i in range(self.sz):
                self.b[i] += ShortSum.cache[self.c][i]
            self.c = 0


class Tree:
    def __init__(self, l, r, branching_factor):
        self.sum = 0
        self.sons = []
        self.sons_sum = ShortSum(branching_factor)
        self.l = l
        self.r = r
        self.branching_factor = branching_factor
        if r - l > 1:
            for i in range(branching_factor):
                sl = l + (r - l) * i // branching_factor
                sr = l + (r - l) * (i + 1) // branching_factor
                self.sons.append(Tree(sl, sr, branching_factor))

    def count(self, ind):
        if self.l == self.r:
            return 0
        if self.l + 1 == self.r:
            return self.sum
        son_ind = ((ind - self.l + 1) * self.branching_factor - 1) // (self.r - self.l)
        return self.sons_sum.prefix(son_ind) + self.sons[son_ind].count(ind)

    def inc(self, ind):
        if self.l == self.r:
            return
        if self.l + 1 == self.r:
            self.sum += 1
            return
        son_ind = ((ind - self.l + 1) * self.branching_factor - 1) // (self.r - self.l)
        self.sons_sum.inc(son_ind)
        self.sons[son_ind].inc(ind)


def counts(L):
    N = len(L)
    logN = int(math.log2(N)) + 1
    sqrtlog = math.isqrt(logN) + 1
    ShortSum.cache = None
    t = Tree(0, 2 * N + 1, sqrtlog)
    ans = []
    for v in L:
        ans.append(t.count(v))
        t.inc(v)
    return ans

Attempt This Online!

The complexity of ShortSum's operations is amortized \$O(1)\$ + a one-time \$o(n)\$ for initialization of cache.

The cost of Tree.__init__ is the number of nodes, which is \$O(n)\$.

The cost of Tree.inc and Tree.prefix each is the depth of the tree, which is \$\log_{\sqrt{\log{n}}}{\log{n}} = O(\frac{\log{n}}{\log \log n})\$.

They are run \$n\$ times, so the total cost is \$O(n \frac{\log{n}}{\log \log n})\$

\$\endgroup\$
1
  • \$\begingroup\$ Very impressive that you coded this so quickly. \$\endgroup\$
    – Simd
    Sep 29, 2023 at 8:41
5
\$\begingroup\$

Python, \$O(n \log n)\$

Simple algorithm based on merge sort that runs in \$O(n \log n)\$ for inputs in any range (assuming comparisons are \$O(1)\$).

def counts_by_value(array: list[int]) -> list[tuple[int, int]]:
    """Returns a list of (index, count) tuples ordered by array[index]."""
    if len(array) == 1:
        return [(0, 0)]

    mid = len(array) // 2
    lcounts = counts_by_value(array[:mid])
    rcounts = counts_by_value(array[mid:])
    lpos = rpos = 0
    counts = []
    while lpos < mid or rpos < len(rcounts):
        if lpos < mid and (
            rpos >= len(rcounts)
            or array[lcounts[lpos][0]] <= array[mid + rcounts[rpos][0]]
        ):
            counts.append(lcounts[lpos])
            lpos += 1
        else:
            counts.append((mid + rcounts[rpos][0], lpos + rcounts[rpos][1]))
            rpos += 1
    return counts


def counts(array: list[int]) -> list[int]:
    """Returns a list of counts ordered by index."""
    return [count for i, count in sorted(counts_by_value(array))]

Attempt This Online!

\$\endgroup\$
1
  • \$\begingroup\$ A great, clean, answer that is also fast. \$\endgroup\$
    – Simd
    Sep 29, 2023 at 8:41

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.