DSA problem
Count of Smaller Numbers After Self
Given an integer array nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are strictly smaller than nums[i].
A brute-force scan compares each element with everything to its right in O(n^2) time. For n up to 10^5 this is too slow — we need a logarithmic-factor improvement. Two classical techniques work: a merge sort that counts inversions during the merge step, and a Binary Indexed Tree over the rank-compressed value space.
The BIT approach is the cleanest. Because values can be negative or huge, first coordinate-compress: collect all distinct values, sort them, and map each to its rank 1..k. Now the universe of values is a dense range from 1 to k where k <= n, making it usable as BIT indices.
Walk the array from right to left. For each nums[i] with compressed rank r, the number of previously-seen values strictly less than nums[i] equals prefix(r - 1) in the BIT — that is exactly how many elements to the right are smaller. After recording the answer, increment the BIT at position r to register the current value. The total work is O(n log n) time and O(n) space, plus O(n log n) for the initial sort.
Examples
nums = [5,2,6,1][2,1,1,0]nums = [-1][0]nums = [-1,-1][0,0]Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.