# Compute how many are no larger than each item in an array

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\$$?

• Under what model is the complexity calculated? Is it the word RAM model? Sep 28 at 18:43
• 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... Sep 28 at 18:44
• @DominicvanEssen I don't believe there's a known $O(n)$ algorithm, although $O(n\log n)$ is known and fairly simple Sep 28 at 18:45
• @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... Sep 28 at 18:54
• This paper describes an O(n sqrt log n) algorithm. Sep 29 at 3:24

# 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})\$$

• Very impressive that you coded this so quickly.
– Simd
Sep 29 at 8:41

# 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!

• A great, clean, answer that is also fast.
– Simd
Sep 29 at 8:41