LeetCode 315: Count of Smaller Numbers After Self

Problem Restatement

We are given an integer array nums.

For each index i, count how many numbers to the right of nums[i] are smaller than nums[i].

Return an array counts, where:

counts[i] = number of smaller elements to the right of nums[i]

For example, in:

nums = [5, 2, 6, 1]

the answer is:

[2, 1, 1, 0]

because:

The official constraints include 1 <= nums.length <= 10^5 and -10^4 <= nums[i] <= 10^4.

Input and Output

Function shape:

def countSmaller(nums: list[int]) -> list[int]:
    ...

Examples

Example 1:

nums = [5, 2, 6, 1]

Output:

[2, 1, 1, 0]

Example 2:

nums = [-1]

Output:

[0]

There is no number to the right.

Example 3:

nums = [-1, -1]

Output:

[0, 0]

The second -1 is equal to the first -1, not smaller.

First Thought: Compare Every Pair

The simplest method is:

1. For every index i.
2. Scan every index j > i.
3. Count values where nums[j] < nums[i].

Code idea:

for i in range(n):
    for j in range(i + 1, n):
        if nums[j] < nums[i]:
            counts[i] += 1

This is correct.

But it costs:

O(n^2)

With n up to 100000, this is too slow.

Key Insight

Process the array from right to left.

When we stand at index i, all numbers to the right have already been seen.

So the problem becomes:

Among the seen numbers, how many are smaller than nums[i]?

We need a data structure that supports:

A Fenwick Tree can do this efficiently if values are mapped into compact integer ranks.

Coordinate Compression

Fenwick Tree uses positive indices.

But nums may contain negative values.

So we compress values into ranks.

For example:

nums = [5, 2, 6, 1]

Sorted unique values:

[1, 2, 5, 6]

Ranks:

Now “values smaller than 5” means “ranks less than 3”.

That can be queried as a prefix sum.

Fenwick Tree Meaning

The Fenwick Tree stores frequencies.

If we have already seen values on the right, then:

tree rank r = how many times value with rank r has appeared

To count numbers smaller than current value:

rank = value_to_rank[nums[i]]
answer[i] = tree.query(rank - 1)

We query rank - 1 because equal values are not smaller.

Then we add the current value into the tree:

tree.add(rank, 1)

Algorithm

1. Sort all unique values in nums.
2. Map each value to rank starting from 1.
3. Create a Fenwick Tree.
4. Create result array counts.
5. Iterate from right to left:
   • Get rank of nums[i].
   • Query how many seen numbers have smaller rank.
   • Store that count in counts[i].
   • Add current rank to the Fenwick Tree.
6. Return counts.

Correctness

When the algorithm processes index i, it has already inserted exactly the elements to the right of i into the Fenwick Tree.

The Fenwick Tree stores frequencies by rank. Since coordinate compression preserves order, a value is smaller than nums[i] exactly when its rank is less than rank(nums[i]).

The query:

tree.query(rank - 1)

returns the total frequency of all seen values with smaller rank. These are exactly the elements to the right of i that are smaller than nums[i].

After storing this count, the algorithm inserts nums[i] into the tree, so it becomes available for indices further left.

Therefore, every counts[i] is computed correctly.

Complexity

Let n = len(nums).

Implementation

class FenwickTree:

    def __init__(self, size: int):
        self.n = size
        self.tree = [0] * (size + 1)

    def add(self, index: int, delta: int) -> None:
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def query(self, index: int) -> int:
        total = 0

        while index > 0:
            total += self.tree[index]
            index -= index & -index

        return total

class Solution:
    def countSmaller(self, nums: list[int]) -> list[int]:
        sorted_values = sorted(set(nums))

        value_to_rank = {
            value: rank
            for rank, value in enumerate(sorted_values, start=1)
        }

        bit = FenwickTree(len(sorted_values))
        counts = [0] * len(nums)

        for i in range(len(nums) - 1, -1, -1):
            rank = value_to_rank[nums[i]]

            counts[i] = bit.query(rank - 1)

            bit.add(rank, 1)

        return counts

Code Explanation

First, collect sorted unique values:

sorted_values = sorted(set(nums))

Then map each value to a compact rank:

value_to_rank = {
    value: rank
    for rank, value in enumerate(sorted_values, start=1)
}

Ranks start at 1 because Fenwick Tree uses 1-based indexing.

Create the tree and answer array:

bit = FenwickTree(len(sorted_values))
counts = [0] * len(nums)

Now scan from right to left:

for i in range(len(nums) - 1, -1, -1):

Get the current value’s rank:

rank = value_to_rank[nums[i]]

Count seen values with smaller rank:

counts[i] = bit.query(rank - 1)

Then insert the current number into the seen set:

bit.add(rank, 1)

The Fenwick Tree methods are standard.

add updates all frequency buckets affected by one rank.

index += index & -index

query sums frequencies from rank 1 through index.

index -= index & -index

Testing

def run_tests():
    s = Solution()

    assert s.countSmaller([5, 2, 6, 1]) == [2, 1, 1, 0]
    assert s.countSmaller([-1]) == [0]
    assert s.countSmaller([-1, -1]) == [0, 0]
    assert s.countSmaller([1, 2, 3, 4]) == [0, 0, 0, 0]
    assert s.countSmaller([4, 3, 2, 1]) == [3, 2, 1, 0]
    assert s.countSmaller([2, 0, 1, 2, 1]) == [3, 0, 0, 1, 0]
    assert s.countSmaller([0, -1, -1, 2]) == [2, 0, 0, 0]

    print("all tests passed")

run_tests()

Test meaning: