DSA Count of Smaller Numbers after Self

The problem

A list of values is given. For each position, the task counts how many values after that position are strictly smaller. The answer is one count per position, in the original order.

Equal values never count. A later copy of the same value is not smaller than the earlier one. Negatives count by ordinary comparison, with no special rule.

cases = [
    ([5, 2, 6, 1], [2, 1, 1, 0]),
    ([4, -1, 3, 4, 0, -2, 3], [5, 1, 2, 3, 1, 0, 0]),
    ([3, 3, 1, 3], [1, 1, 0, 0]),
    ([1, 2, 3], [0, 0, 0]),
    ([3, 2, 1], [2, 1, 0]),
]
for values, expected in cases:
    print("values:", values, "counts:", expected)

The duplicate case pins the strict rule down. Each 3 counts only the single 1 after it. The last position always counts zero, because nothing stands after it.

Intuition: look right and count, with one trap

The first idea looks right from each position and counts the smaller values there. The idea is correct and simple. Its hidden trap is the word smaller, which careless code reads as smaller or equal.

Counting equals inflates every duplicate. The run below shows both versions on the duplicate case. Only one of them matches the problem.

values = [3, 3, 1, 3]
strict = [sum(1 for j in range(i + 1, len(values)) if values[j] < values[i])
          for i in range(len(values))]
loose = [sum(1 for j in range(i + 1, len(values)) if values[j] <= values[i])
         for i in range(len(values))]
print("values:", values)
print("strictly smaller counts:", strict)
print("smaller-or-equal counts:", loose)

The loose version credits each 3 with the later 3s. Those credits are exactly the error the strict rule forbids. Any fast method must preserve the strict line, not just the counting.

Brute force: every pair, compared once

The brute force is the intuition written plainly. Two nested loops compare each value with every value after it. A counter records the comparisons.

def brute(values):
    counts = [0] * len(values)
    compared = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            compared += 1
            if values[j] < values[i]:
                counts[i] += 1
    return counts, compared

for values in [[5, 2, 6, 1], [4, -1, 3, 4, 0, -2, 3]]:
    counts, compared = brute(values)
    print("values:", values, "counts:", counts, "comparisons:", compared)

Seven values already cost 21 comparisons. The count grows with the square of the list length, because each new value compares against everything after it. The optimal method replaces comparisons with rank arithmetic.

The optimal solution: compress to ranks, count from the right with a Fenwick tree

Coordinate compression replaces each value by its rank among the sorted distinct values, and scanning from the right with a Fenwick tree holding one count per rank turns each answer into a prefix count below the current rank. That one sentence is the whole method.

A Fenwick tree is an array where each slot stores the count of a short range of ranks, so a prefix count adds a few slots instead of scanning all ranks. Equal values share one rank, so the prefix below that rank never counts them. The strict rule survives by construction.

Ranks in this article start at zero for the Python code. The tree shifts them by one internally, because its slot arithmetic walks upward from index 1.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
        self.steps = 0

    def add(self, index, delta):
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            self.steps += 1
            i += i & -i

    def prefix(self, k):
        total = 0
        i = k
        while i > 0:
            total += self.tree[i]
            self.steps += 1
            i -= i & -i
        return total

def count_smaller(values):
    unique = sorted(set(values))
    rank = {v: i for i, v in enumerate(unique)}
    fw = Fenwick(len(unique))
    counts = [0] * len(values)
    for i in range(len(values) - 1, -1, -1):
        r = rank[values[i]]
        counts[i] = fw.prefix(r)
        fw.add(r, 1)
    return counts, fw.steps

cases = [
    [5, 2, 6, 1],
    [4, -1, 3, 4, 0, -2, 3],
    [3, 3, 1, 3],
    [1, 2, 3],
    [3, 2, 1],
]
for values in cases:
    counts, steps = count_smaller(values)
    print("values:", values, "counts:", counts, "fenwick steps:", steps)

Every case matches the first section, duplicates and negatives included. The step counts stay below the brute force's comparison counts at the same sizes. The gap widens with length, as the complexity section counts.

Walkthrough: scanning [5, 2, 6, 1] from the right

The scan starts at the last value. The tree holds exactly the values already passed, which are exactly the values after the current position. Each step prints the count below the current rank, then adds the current value.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
        self.steps = 0

    def add(self, index, delta):
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            self.steps += 1
            i += i & -i

    def prefix(self, k):
        total = 0
        i = k
        while i > 0:
            total += self.tree[i]
            self.steps += 1
            i -= i & -i
        return total

def count_smaller(values):
    unique = sorted(set(values))
    rank = {v: i for i, v in enumerate(unique)}
    fw = Fenwick(len(unique))
    counts = [0] * len(values)
    for i in range(len(values) - 1, -1, -1):
        r = rank[values[i]]
        counts[i] = fw.prefix(r)
        fw.add(r, 1)
    return counts, fw.steps

values = [5, 2, 6, 1]
unique = sorted(set(values))
rank = {v: i for i, v in enumerate(unique)}
print("sorted unique:", unique, "ranks:", [rank[v] for v in values])
fw = Fenwick(len(unique))
freq = [0] * len(unique)
counts = [0] * len(values)
for i in range(len(values) - 1, -1, -1):
    r = rank[values[i]]
    counts[i] = fw.prefix(r)
    print("value", values[i], "rank", r, "smaller after:", counts[i],
          "rank counts before adding:", freq)
    fw.add(r, 1)
    freq[r] += 1
print("counts:", counts)

The first value scanned, 1, finds an empty tree and counts zero. The value 5, scanned last, finds 2 and 1 below its rank and counts two. The answer assembles itself in reverse, one prefix count at a time.

Complexity

Each value costs one prefix count and one update, and each of those walks O(log m) tree slots for m distinct values, so total time is O(n log n). The tree holds one slot per distinct value, so extra space is O(n).

The brute force makes one comparison per pair. Its time is O(n^2), and the counts below put the two bills side by side.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
        self.steps = 0

    def add(self, index, delta):
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            self.steps += 1
            i += i & -i

    def prefix(self, k):
        total = 0
        i = k
        while i > 0:
            total += self.tree[i]
            self.steps += 1
            i -= i & -i
        return total

def count_smaller(values):
    unique = sorted(set(values))
    rank = {v: i for i, v in enumerate(unique)}
    fw = Fenwick(len(unique))
    counts = [0] * len(values)
    for i in range(len(values) - 1, -1, -1):
        r = rank[values[i]]
        counts[i] = fw.prefix(r)
        fw.add(r, 1)
    return counts, fw.steps

for n in [10, 20, 40]:
    values = list(range(n, 0, -1))
    counts, steps = count_smaller(values)
    print("values", n, "- brute comparisons:", n * (n - 1) // 2,
          " fenwick steps:", steps, " first count:", counts[0])

Descending lists are the brute force's worst shape and the scan's routine case. At 40 values the bills stand at 780 comparisons against a few hundred tree steps, and the tree steps grow by a logarithm, not a square.

Edge cases and pitfalls

An empty list answers an empty list. A list of one value answers a single zero. Both fall out of the scan with no special casing, because the tree starts empty either way.

Querying the prefix up to and including the current rank is the classic off-by-one. It counts equals as smaller whenever a duplicate was scanned earlier. The query must stop strictly below the rank.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
        self.steps = 0

    def add(self, index, delta):
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            self.steps += 1
            i += i & -i

    def prefix(self, k):
        total = 0
        i = k
        while i > 0:
            total += self.tree[i]
            self.steps += 1
            i -= i & -i
        return total

def count_smaller(values):
    unique = sorted(set(values))
    rank = {v: i for i, v in enumerate(unique)}
    fw = Fenwick(len(unique))
    counts = [0] * len(values)
    for i in range(len(values) - 1, -1, -1):
        r = rank[values[i]]
        counts[i] = fw.prefix(r)
        fw.add(r, 1)
    return counts, fw.steps

print("empty:", count_smaller([])[0])
print("single:", count_smaller([9])[0])
print("all equal:", count_smaller([4, 4, 4])[0])
print("ascending:", count_smaller([1, 2, 3, 4])[0])
print("descending:", count_smaller([4, 3, 2, 1])[0])
print("negatives:", count_smaller([-1, -5, 0])[0])

Negatives need no shifting or offset. Compression ranks them by sorted order like any other values. The sorted distinct list, not the raw value, drives every index the tree sees.