← DSA Atlas
Dedicated problem page · #315

Count of Smaller Numbers After Self

HardAdvanced Range Data StructuresCount smaller to the rightFenwick tree over compressed ranks (right-to-left)
Solve on LeetCode ↗
315
HardAdvanced Range Data StructuresFenwick tree over compressed ranks (right-to-left)Count smaller to the right

Count of Smaller Numbers After Self

Given an integer array nums, return a new array counts where counts[i] is the number of elements to the right of nums[i] that are strictly smaller than nums[i].

Open official problem prompt ↗
In plain English

For every position, count how many values appearing later in the array are strictly smaller than it.

Picture it like this

Walk backward through a line of people, keeping a tally sheet bucketed by height. Before adding yourself, glance at the sheet and sum every bucket shorter than you — that is how many shorter people already stand ahead (to your right).

Example
Input
nums = [5,2,6,1]
Output
[2,1,1,0]
Why
Right of 5 are {2,1} smaller (2); right of 2 is {1} (1); right of 6 is {1} (1); right of 1 nothing (0).
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Pattern lesson

See the pattern, then code

Count smaller to the right
Recognition clue

Counting, for each element, how many later elements are smaller is an inversion-style query answerable by a Fenwick tree over value ranks or by merge sort.

↗
Advanced Range Data Structures

Online prefix or range queries with updates, inversions, or coordinate compression.. Scan right to left, inserting each value's rank into a Fenwick tree. Before inserting nums[i], the tree already holds every element to its right, so a prefix query for ranks below nums[i] counts the smaller ones instantly.

New words, made simpleKnow these before the algorithm
Coordinate compression
Mapping arbitrary values to small consecutive ranks so a Fenwick tree fits in O(k) space.
Rank
The 1-based position of a value among the sorted distinct values.
Inversion
A pair (i, j) with i < j but nums[i] > nums[j]; this problem counts inversions per left index.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute force pairs

Quadratic; times out at n = 10^5.

For each i, scan all j > i and count smaller values.

Time O(n^2)Space O(1)
Merge sort with counting

Works well; slightly more bookkeeping to attribute counts to original indices.

Count cross-pair inversions while merging sorted halves of index-value pairs.

Time O(n log n)Space O(n)
Best choiceFenwick tree over ranks

Direct and clean once values are compressed to ranks.

Insert values right to left and prefix-query smaller ranks.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

When processing index i (right to left), the Fenwick tree contains exactly the multiset of elements at indices > i, so query(rank(nums[i]) - 1) equals the number of strictly-smaller elements to the right.

Why this is correct

Reasoning

Right-to-left insertion guarantees the tree's contents are precisely the elements already to the right of the current one. A prefix query over ranks strictly below the current rank counts those with smaller value, and coordinate compression keeps rank comparisons faithful to value comparisons.

The algorithm in three movesSay these aloud before coding
1Compress the distinct values into ranks 1..k with sorted order

see 1: query(<1)=0, insert 1

2Create a Fenwick tree indexed by rank

see 6: query(<6)=1, insert 6

3Iterate nums from right to left

see 2: query(<2)=1, insert 2

4For each value query the count of ranks strictly less than its rank, then insert its rank

see 5: query(<5)=2

5Reverse the collected counts to restore original order

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
50
21
62
13
1 · Readx=1, rank=1
2 · Askranks < 1?
3 · Update statetree empty
4 · Resultcount 0, insert rank 1
Key takeaway

Processing right to left, the Fenwick tree already contains all elements to the right when each query runs.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-6Compress to ranks

    Sort the distinct values and map each to a 1-based rank so the tree is small and dense.

  2. 2
    Lines 9-12update

    Insert one occurrence of a rank, propagating up the tree.

  3. 3
    Lines 14-19query

    Count how many inserted elements have rank <= i by summing partial blocks.

  4. 4
    Lines 21-25Reverse sweep

    Query before insert so only right-side elements are counted, then reverse to restore order.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single element yields [0]
  • All equal values yield all zeros since none are strictly smaller
  • Strictly decreasing input yields the maximal per-index counts n-1, n-2, ...
  • Negative values are handled by compression, not by array offset
!

Common beginner mistakes

  • Querying rank instead of rank-1, which counts equal values as smaller
  • Inserting before querying, contaminating the count with the current element
  • Forgetting to reverse the result after the right-to-left pass
  • Sizing the tree by value range instead of compressed ranks, wasting memory or overflowing indices
Check your understanding

Why does scanning right to left, querying before inserting, give the count of smaller elements to the right?

More in Advanced Range Data Structures

#218The Skyline ProblemSweep line with max-heap#307Range Sum Query – MutablePoint update, prefix-sum query#327Count of Range SumCount prefix-sum pairs in range#493Reverse PairsCount significant inversions#699Falling SquaresRange assign, range max#715Range ModuleMerge and split disjoint intervals