Count of Smaller Numbers After Self

Hard· Fenwick tree· coordinate compression

Problem

For every element of an integer array, count how many elements to its right are strictly smaller. Return these counts as an array of the same length.

Examples

Input: nums = [5,2,6,1]

Output: [2,1,1,0]

Input: nums = [-1,-1]

Output: [0,0]

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Hints & approach

Hint 1

Process the array from right to left so everything "after" has already been seen.

Hint 2

You need: how many seen values are less than x? That is a prefix count over values.

Hint 3

Compress values to ranks and keep counts in a Fenwick tree indexed by rank.

Approachtry the hints first

Map each value to its rank among the sorted distinct values (or offset by 10^4 since the range is small). Walk from right to left: the answer for x is the Fenwick prefix sum of counts for ranks below rank(x); then add 1 at rank(x). Each element costs two O(log n) tree operations. A merge-sort that counts right-side elements moved ahead of each left element is an alternative.

Time O(n log n) · Space O(n)

← PreviousRange Sum Query - Mutable Next →Reverse Pairs