For each element in the array, we need to count how many elements to its right are strictly smaller. The result is an array of the same length where each position holds that count.

The direct method scans everything to the right of each element and counts. With up to 100,000 elements, that is an O(n^2) algorithm, up to 10 billion comparisons.

Processing the array from right to left reframes the problem as a sequence of rank queries: how many of the elements seen so far are smaller than the current one? A structure that answers rank queries in O(log n), such as a Binary Indexed Tree, solves it directly. Merge sort solves it from a different angle, by counting inversions while it sorts.

Key Constraints:

Intuition

Scan every element to the right of each position and count how many are smaller. This translates the problem statement into two nested loops: for position i, iterate from i + 1 to the end, incrementing a counter each time a value is strictly less than nums[i].

Algorithm

Example Walkthrough

Code

Each scan starts from scratch; nothing learned while counting for one element carries over to the next. The remaining approaches share work across elements in two different ways: merge sort counts every qualifying pair as a side effect of sorting, and a Binary Indexed Tree answers each count incrementally in O(log n).

Intuition

Counting smaller elements to the right is inversion counting. An inversion is a pair (i, j) where i < j but nums[i] > nums[j], and counts[i] is the number of inversions that have i as the left index.

Merge sort counts inversions as a byproduct of merging. When the merge step places an element from the left half into the merged result, every element already placed from the right half is smaller than it and sat to its right in the original array. Adding that running count to the left element's answer accumulates the result.

Sorting rearranges the elements, so each one carries its original index: we sort (value, original index) pairs and accumulate counts into the result array at the original indices.

Algorithm

Example Walkthrough

Code

Merge sort computes all the counts in one pass over the recursion, at the cost of threading original indices through the sort. The last approach skips sorting entirely: insert elements one at a time and query "how many values smaller than X are already present?" in O(log n).

Intuition

Traverse the array from right to left. Before inserting each element, count how many already-inserted values are smaller. Every value inserted so far came from an index further right, so that count is the answer for the current position.

A Binary Indexed Tree (BIT) supports both required operations in O(log M), where M is the size of the index range: point update (add 1 at a position) and prefix sum query (sum of all values from index 1 to k). Index the BIT by value, treating it as a frequency table: inserting an element adds 1 at position value, and counting strictly smaller elements is the prefix sum from 1 to value - 1. Querying up to value - 1 rather than value is what excludes duplicates of the current element from the count.

Values can be negative (down to -10,000), so we add 10,001 to every value, mapping the range to [1, 20,001]. The shift starts at 1 rather than 0 because a BIT is 1-indexed: its traversal loops strip the lowest set bit until the index reaches 0, so index 0 can never store data.

The same approach works when values are unbounded. Sort the distinct values, replace each value with its rank (coordinate compression), and the BIT only needs n positions instead of one per possible value.

Algorithm

Example Walkthrough

Code