Count of Smaller Numbers After Self
Hard · Arrays & Hashing · Array · Binary Search · Divide and Conquer · Binary Indexed Tree · Segment Tree · Merge Sort · Ordered Set
Problem
Given an integer array nums, return an array counts where counts[i] is the number of elements to the right of index i that are strictly smaller than nums[i].
Examples
Input: nums = [4,1,3,2] Output: [3,0,1,0]
Everything after 4 is smaller. After 1 nothing is smaller. After 3 only the 2 is.
Input: nums = [-2,-2] Output: [0,0]
Equal values do not count as smaller.
Input: nums = [5,2,6,1] Output: [2,1,1,0]
After 5: 2 and 1. After 2: 1. After 6: 1. Nothing follows 1.
Constraints
- 1 <= len(nums) <= 10^5
- -10^4 <= nums[i] <= 10^4
Approaches
- Baseline: compare every pair — time O(n²), space O(1) besides the output
Follow-up
If the values were huge (say up to 10^9), sort the distinct values and replace each by its rank first (coordinate compression); the Fenwick tree then has at most n positions. Merge sort also solves it in O(n log n): while merging, each element of the left half gains one for every element of the right half already placed before it, and that count is exactly the smaller elements to its right.
Related problems
Start free on Cariara · Coding problems · System design studio
