315. Count of Smaller Numbers After Self

Problem¶

For each element, count how many strictly smaller elements appear to its right.

[5, 2, 6, 1] -> [2, 1, 1, 0]
# 5 has two smaller values to its right: 2 and 1.

Key trick¶

Scan from right to left while a Fenwick tree stores frequencies by compressed value rank; the prefix sum before the current rank gives the number of strictly smaller values already seen.

Trap¶

Counting equal values as smaller by querying through the current rank instead of stopping before it.
Using values directly as indices without handling negatives or a large value range.
Updating all larger keys in a map, which can degrade to \(O(n^2)\).

Why is it interesting?¶

It transforms a quadratic comparison problem into dynamic prefix-frequency queries, combining coordinate compression with a Fenwick tree.

Python solution¶

class Solution:
    def countSmaller(self, nums: list[int]) -> list[int]:
        # Compress values into 1-based ranks so negatives and gaps do not matter.
        rank = {x: i + 1 for i, x in enumerate(sorted(set(nums)))}
        tree = [0] * (len(rank) + 1)
        ans = [0] * len(nums)

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

            # Query ranks strictly below idx.
            j = idx - 1
            while j > 0:
                ans[i] += tree[j]
                j -= j & -j

            # Add the current value to the frequencies.
            j = idx
            while j < len(tree):
                tree[j] += 1
                j += j & -j

        return ans

Time: \(O(n \log n)\)
Space: \(O(n)\)

Comment on my solution¶

The right-to-left scan is the correct starting point because all processed elements are exactly those to the current element's right.
A plain map cannot efficiently count all keys below a value; it needs an ordered structure such as a Fenwick tree.
Modeling every smaller pair as a graph edge requires up to \(O(n^2)\) edges.
The count is not generally a longest-path length, and topological sorting does not provide the required per-index counts.
The submitted method is incomplete because it does not compute or return a result.

# Ideas
# - Brute force is O(n^2)
# - As I've just learnt about Khan's topological order and this
#   problem is in the section trees and graphs
#   - maybe we can see nums as a directed graph where edges are
#     from later and smaller node
#     - and the indegree of each node i is counts[i]
#     - this is also the length of the longest path to nums[i]
# - maybe scan right-to-left
#   - keep a map of number -> how many inferior to it so far

class Solution:
    def countSmaller(self, nums: list[int]) -> list[int]:
        # [5,2,6,1] -> [2,1,1,0]
        # [-1] -> [0]
        # [-1,-1] -> [0,0]

Extra¶

I didn't know about Fenwick trees¶

Ok I couldn't have found this solution, first time I hear about Fenwick trees. Can you define them and explain me why they are the right tool for this problem?

Fenwick tree definition¶

A Fenwick tree, also called a Binary Indexed Tree, maintains frequencies or sums while supporting two operations efficiently:

Add a value at one position.
Compute the sum from the beginning through a position.

Both operations take \(O(\log n)\) instead of \(O(n)\).

How this problem becomes a prefix-sum problem¶

Process the array from right to left.

When examining a value x, the data structure contains exactly the values to its right. We need:

A query: how many stored values are smaller than x?
An update: insert x.

If values were small positive indices, we could store their frequencies:

value:      1  2  3  4  5  6
frequency:  1  1  0  0  0  1

The number smaller than 5 is the prefix sum through value 4.

A dictionary can store each frequency, but answering “how many keys are below x?” requires scanning many keys. A Fenwick tree calculates that prefix sum in \(O(\log n)\).

Coordinate compression¶

The input can contain negatives and large gaps, so values cannot conveniently be used as array indices.

Sort the distinct values and assign each one a rank:

values:  [1, 2, 5, 6]
ranks:    1  2  3  4

Only ordering matters:

x < y  exactly when  rank[x] < rank[y]

Therefore, the number of values smaller than x is the frequency sum through:

rank[x] - 1

Using the previous rank is important because equal values are not smaller.

What the Fenwick tree stores¶

For a normal frequency array, each position stores one frequency.

A Fenwick tree instead stores sums over carefully chosen ranges. For a 1-based index i, the range represented by tree[i] has length:

i & -i

This expression extracts the lowest set bit of i.

For example:

tree[1] stores frequencies [1..1]
tree[2] stores frequencies [1..2]
tree[3] stores frequencies [3..3]
tree[4] stores frequencies [1..4]
tree[5] stores frequencies [5..5]
tree[6] stores frequencies [5..6]
tree[8] stores frequencies [1..8]

These overlapping ranges let us build any prefix from only \(O(\log n)\) stored sums.

Prefix-sum query¶

To get the sum through index i:

Add tree[i].
Remove the lowest set bit from i.
Repeat until i becomes zero.

def query(i):
    total = 0
    while i > 0:
        total += tree[i]
        i -= i & -i
    return total

For prefix 7, the visited indices are:

7 -> 6 -> 4 -> 0

Their represented ranges are:

[7..7] + [5..6] + [1..4] = [1..7]

Point update¶

To add one occurrence at rank i:

Update tree[i].
Move to the next range containing i.
Repeat until leaving the tree.

def add(i):
    while i < len(tree):
        tree[i] += 1
        i += i & -i

Updating rank 5 in a tree of size 8 visits:

5 -> 6 -> 8

Those are exactly the stored ranges that include position 5.

Walkthrough¶

For:

nums = [5, 2, 6, 1]

Compression gives:

1 -> 1
2 -> 2
5 -> 3
6 -> 4

Scan from right to left:

Current value	Rank	Query through	Smaller values seen	Result
1	1	0	none	0
6	4	3	1	1
2	2	1	1	1
5	3	2	1, 2	2

So the answer is:

[2, 1, 1, 0]

Why it is the right tool¶

The core pattern is:

Repeatedly update one position
+
Repeatedly query a prefix sum

That is precisely what a Fenwick tree is designed for.

A plain list gives \(O(1)\) updates but \(O(n)\) prefix queries.
Precomputed prefix sums give \(O(1)\) queries but \(O(n)\) after each update.
A Fenwick tree gives \(O(\log n)\) for both.
Coordinate compression turns arbitrary values into valid ordered indices.

The full algorithm therefore takes \(O(n \log n)\) time and \(O(n)\) space. Fenwick trees are not something you would normally derive from scratch during this problem; the interview skill is recognizing the dynamic prefix-sum pattern once you know the data structure.

A bit more about Fenwick and their application in the above algorithm¶

Thanks. But not much clearer to me.

1) I don't understand how the ranges are picked and why ~i & -i~ as range length makes sens. 2) I can't visualize the (left / right) tree branches. 3) I don't understand how the tree is built over time (while scanning right to left) 4) Can you go through the example ~[5, 2, 6, 1]~ step by step, specifically showing the tree being built.

The main missing idea is that a Fenwick tree is not a normal binary tree with left and right children. It is an array of overlapping range sums, with parent relationships implied by binary arithmetic.

1. How are the ranges chosen?¶

For each index \(i\), define:

\[ \operatorname{lowbit}(i) = i \mathbin{\&} (-i) \]

This gives the largest power of two dividing \(i\).

i   binary   lowbit(i)   stored range
1   0001         1       [1..1]
2   0010         2       [1..2]
3   0011         1       [3..3]
4   0100         4       [1..4]
5   0101         1       [5..5]
6   0110         2       [5..6]
7   0111         1       [7..7]
8   1000         8       [1..8]

The range stored at position \(i\) is:

\[ [i-\operatorname{lowbit}(i)+1,\ i] \]

For example, \(6\) in binary is:

 6 = 0110
-6 = 1010
-----------
 & = 0010 = 2

Therefore, position \(6\) stores a range of length \(2\) ending at \(6\):

[5..6]

These ranges are not discovered from the input. They are a fixed design that breaks every prefix into a small number of power-of-two blocks.

For example:

prefix [1..7]
    = [1..4] + [5..6] + [7..7]
    = tree[4] + tree[6] + tree[7]

The query obtains those blocks by repeatedly subtracting the low bit:

7 -> 6 -> 4 -> 0

Each subtraction removes one set bit, so there are at most \(O(\log n)\) steps.

2. Where are the left and right branches?¶

There are no conventional left and right branches.

For a Fenwick tree of size \(4\), the stored ranges are:

tree[1] stores [1..1]
tree[2] stores [1..2]
tree[3] stores [3..3]
tree[4] stores [1..4]

The update-parent relationships can be visualized as:

1 -> 2 -> 4
3 ------> 4

Or as an implicit hierarchy:

4 stores [1..4]
├── 2 stores [1..2]
│   └── 1 stores [1..1]
└── 3 stores [3..3]

This is not a binary search tree. The word “tree” refers to the implicit hierarchy among aggregated ranges.

When adding a value at position \(i\), the next aggregate containing it is found by:

\[ i \leftarrow i+\operatorname{lowbit}(i) \]

For example, updating position \(1\) updates:

1 -> 2 -> 4

Those ranges all contain position \(1\):

[1..1]
[1..2]
[1..4]

Updating position \(3\) updates:

3 -> 4

Those ranges both contain position \(3\):

[3..3]
[1..4]

3. How is the tree built over time?¶

It starts with zeros. There is no separate construction step.

While scanning right to left:

Query how many previously seen values have a smaller rank.
Add the current value's rank to the tree.

The tree therefore represents only the elements already encountered, which are exactly the elements to the current position's right.

For four ranks, the meaning of the tree array is always:

tree[1] = count at rank 1
tree[2] = count at ranks 1 through 2
tree[3] = count at rank 3
tree[4] = count at ranks 1 through 4

It is important that tree is not the raw frequency array. Its entries are aggregate counts.

4. Complete walkthrough of `[5, 2, 6, 1]`¶

First, compress the values into ranks:

value:  1  2  5  6
rank:   1  2  3  4

Thus:

5 -> rank 3
2 -> rank 2
6 -> rank 4
1 -> rank 1

We scan in this order:

1, 6, 2, 5

Initially:

raw rank frequencies: [0, 0, 0, 0]
Fenwick tree:          [0, 0, 0, 0]

The displayed tree omits its unused index \(0\).

Process `1`¶

Its rank is \(1\).

To count values strictly smaller than rank \(1\), query through rank \(0\):

query path: none
smaller count: 0

Now insert rank \(1\). The update path is:

1 -> 2 -> 4

Increment those tree positions:

raw rank frequencies: [1, 0, 0, 0]
Fenwick tree:          [1, 1, 0, 1]

Interpretation:

tree[1] = 1 value in rank [1..1]
tree[2] = 1 value in ranks [1..2]
tree[3] = 0 values in rank [3..3]
tree[4] = 1 value in ranks [1..4]

The partial answer is:

[?, ?, ?, 0]

Process `6`¶

Its rank is \(4\).

Strictly smaller ranks are \(1\) through \(3\), so query prefix \(3\).

The query path is:

3 -> 2 -> 0

Read:

tree[3] + tree[2]
= 0 + 1
= 1

The one smaller value is 1.

Now insert rank \(4\). Its update path is only:

The state becomes:

raw rank frequencies: [1, 0, 0, 1]
Fenwick tree:          [1, 1, 0, 2]

The partial answer is:

[?, ?, 1, 0]

Process `2`¶

Its rank is \(2\).

Strictly smaller ranks end at rank \(1\), so query prefix \(1\).

query path: 1 -> 0
tree[1] = 1
smaller count: 1

The smaller value is 1.

Now insert rank \(2\). The update path is:

2 -> 4

The state becomes:

raw rank frequencies: [1, 1, 0, 1]
Fenwick tree:          [1, 2, 0, 3]

Notice:

tree[2] = 2

It represents ranks \(1\) through \(2\), containing 1 and 2.

The partial answer is:

[?, 1, 1, 0]

Process `5`¶

Its rank is \(3\).

Strictly smaller ranks are \(1\) through \(2\), so query prefix \(2\).

query path: 2 -> 0
tree[2] = 2
smaller count: 2

The two smaller values are 1 and 2.

Now insert rank \(3\). The update path is:

3 -> 4

The final state is:

raw rank frequencies: [1, 1, 1, 1]
Fenwick tree:          [1, 2, 1, 4]

The final answer is:

[2, 1, 1, 0]

The entire execution can be summarized as:

value   rank   queried prefix   query result   update path   tree after update
1       1      [none]           0              1, 2, 4       [1, 1, 0, 1]
6       4      [1..3]           1              4             [1, 1, 0, 2]
2       2      [1..1]           1              2, 4          [1, 2, 0, 3]
5       3      [1..2]           2              3, 4          [1, 2, 1, 4]

The essential distinction is:

Raw frequencies tell us how many times each rank occurred.

The Fenwick tree stores overlapping sums of those frequencies,
allowing prefix totals to be read and updated in O(log n).

how the answer is built¶

In the "Complete walkthrough of [5, 2, 6, 1]" section, one thing is not clear to me:

How ans array is built? We build the raw rank freqencies tree, and then Fenwick tree which end up being [1, 2, 1, 4], but how the answer [2, 1, 1, 0] is built?

The answer is not computed from the final Fenwick tree. Each answer entry is produced during the right-to-left scan and immediately stored at the current original index.

Start with:

nums = [5, 2, 6, 1]
index    0  1  2  3

ans  = [0, 0, 0, 0]

We visit indices in reverse:

3, 2, 1, 0

At each index:

Query the Fenwick tree for the number of smaller values already seen.
Store that query result in ans[i].
Insert the current value into the Fenwick tree.

Index `3`, value `1`¶

The tree contains no values yet because nothing is to the right of 1.

smaller count = 0
ans[3] = 0

ans = [0, 0, 0, 0]

Then insert 1 into the tree.

Index `2`, value `6`¶

The tree currently represents:

[1]

There is one smaller value:

smaller count = 1
ans[2] = 1

ans = [0, 0, 1, 0]

Then insert 6.

Index `1`, value `2`¶

The tree currently represents:

[6, 1]

Only 1 is smaller than 2:

smaller count = 1
ans[1] = 1

ans = [0, 1, 1, 0]

Then insert 2.

Index `0`, value `5`¶

The tree currently represents:

[2, 6, 1]

The values 2 and 1 are smaller than 5:

smaller count = 2
ans[0] = 2

ans = [2, 1, 1, 0]

Then insert 5.

Combined view¶

i   nums[i]   values already in tree   query result   ans after query
3      1      []                       0              [0, 0, 0, 0]
2      6      [1]                      1              [0, 0, 1, 0]
1      2      [1, 6]                   1              [0, 1, 1, 0]
0      5      [1, 2, 6]                2              [2, 1, 1, 0]

The corresponding code structure is:

ans = [0] * len(nums)

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

    # The tree currently contains only elements to index i's right.
    ans[i] = query(idx - 1)

    # Make nums[i] available when processing earlier indices.
    add(idx)

The final Fenwick tree:

[1, 2, 1, 4]

only says that all four ranks have now been inserted. It does not directly contain:

[2, 1, 1, 0]

That answer comes from the four prefix queries made at different moments during the scan.

Pattern to solve problems with Fenwick trees¶

Now that you know what I was missing and misunderstanding, explain the whole algorithm again but in a concise way such that I can apply it to other problem.

The reusable pattern¶

Use a Fenwick tree when a problem repeatedly asks you to:

Insert or update a value.
Count or sum everything below some value.
Preserve the ordering of values.

For this problem, scanning right to left turns:

Count smaller elements to the right.

into:

Among the values already inserted, how many are smaller than the current value?

1. Establish the scan invariant¶

Scan from right to left.

Before processing index \(i\), the Fenwick tree contains exactly:

\[ \text{nums}[i+1:] \]

Therefore, a query at index \(i\) counts only elements to its right.

The order is:

Query the tree.
Store the result in ans[i].
Insert nums[i] into the tree.

The answer is built from query results over time, not from the final tree.

2. Compress values into ranks¶

Fenwick tree indices must be small positive integers, but input values may be negative, duplicated, or widely separated.

Map each distinct value to its sorted rank:

values:  [1, 2, 5, 6]
ranks:    1  2  3  4

Ranks preserve comparisons:

\[ x < y \iff \operatorname{rank}(x) < \operatorname{rank}(y) \]

3. Treat the tree as a frequency structure¶

In this problem, inserting rank \(r\) means increasing its frequency by one.

The Fenwick tree supports:

add(r, 1): insert one occurrence of rank \(r\).
query(r): count inserted values with ranks from \(1\) through \(r\).

To count values strictly smaller than rank \(r\), use:

\[ \operatorname{query}(r-1) \]

Using \(r-1\) excludes duplicates of the current value.

4. Fenwick tree mechanics¶

Each entry stores the sum of a fixed range ending at that index:

\[ \text{tree}[i] = \text{sum over } [i-\operatorname{lowbit}(i)+1,\ i] \]

where:

\[ \operatorname{lowbit}(i)=i\mathbin{\&}(-i) \]

There are no normal left and right branches. Binary arithmetic determines which aggregate ranges to visit.

def query(i):
    total = 0
    while i > 0:
        total += tree[i]
        i -= i & -i
    return total


def add(i, delta):
    while i < len(tree):
        tree[i] += delta
        i += i & -i

A query moves toward smaller prefix blocks.
An update moves toward larger ranges containing the updated position.
Both take \(O(\log n)\).

5. Apply it to the example¶

nums = [5, 2, 6, 1]
ranks = {1: 1, 2: 2, 5: 3, 6: 4}

Scan right to left:

i   value   rank   inserted values   query(rank - 1)   ans[i]
3     1       1    []                 0                 0
2     6       4    [1]                1                 1
1     2       2    [1, 6]             1                 1
0     5       3    [1, 2, 6]          2                 2

This produces:

ans = [2, 1, 1, 0]

Complete implementation¶

class Solution:
    def countSmaller(self, nums: list[int]) -> list[int]:
        ranks = {x: i + 1 for i, x in enumerate(sorted(set(nums)))}
        tree = [0] * (len(ranks) + 1)
        ans = [0] * len(nums)

        def query(i: int) -> int:
            total = 0
            while i > 0:
                total += tree[i]
                i -= i & -i
            return total

        def add(i: int) -> None:
            while i < len(tree):
                tree[i] += 1
                i += i & -i

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

            # The tree contains exactly the elements to index i's right.
            ans[i] = query(rank - 1)
            add(rank)

        return ans

Time: \(O(n \log n)\)
Space: \(O(n)\)

How to reuse the pattern¶

After compressing values to ranks, a Fenwick frequency tree can answer:

Values less than \(x\):

\[ \operatorname{query}(\operatorname{rank}(x)-1) \]

Values less than or equal to \(x\):

\[ \operatorname{query}(\operatorname{rank}(x)) \]

Values greater than \(x\):

\[ \text{inserted count} - \operatorname{query}(\operatorname{rank}(x)) \]

Values greater than or equal to \(x\):

\[ \text{inserted count} - \operatorname{query}(\operatorname{rank}(x)-1) \]

The general recipe is:

Choose a scan direction so the tree represents the relevant past or future.
Compress values if necessary.
Convert the required comparison into a prefix query.
Save the query result for the current position.
Update the tree with the current value.

315. Count of Smaller Numbers After Self

Problem¶

Key trick¶

Trap¶

Why is it interesting?¶

Python solution¶

Comment on my solution¶

Extra¶

I didn't know about Fenwick trees¶

Fenwick tree definition¶

How this problem becomes a prefix-sum problem¶

Coordinate compression¶

What the Fenwick tree stores¶

Prefix-sum query¶

Point update¶

Walkthrough¶

Why it is the right tool¶

A bit more about Fenwick and their application in the above algorithm¶

1. How are the ranges chosen?¶

2. Where are the left and right branches?¶

3. How is the tree built over time?¶

4. Complete walkthrough of [5, 2, 6, 1]¶

Process 1¶

Process 6¶

Process 2¶

Process 5¶

how the answer is built¶

Index 3, value 1¶

Index 2, value 6¶

Index 1, value 2¶

Index 0, value 5¶

Combined view¶

Pattern to solve problems with Fenwick trees¶

The reusable pattern¶

1. Establish the scan invariant¶

2. Compress values into ranks¶

3. Treat the tree as a frequency structure¶

4. Fenwick tree mechanics¶

5. Apply it to the example¶

Complete implementation¶

How to reuse the pattern¶

4. Complete walkthrough of `[5, 2, 6, 1]`¶

Process `1`¶

Process `6`¶

Process `2`¶

Process `5`¶

Index `3`, value `1`¶

Index `2`, value `6`¶

Index `1`, value `2`¶

Index `0`, value `5`¶