The problem
For each element of an array, count how many elements to its RIGHT are strictly smaller. Return the array of counts.
Stuck? Reveal hints one at a time
How to approach it
- 1Coordinate-compress the values into ranks 1..m (handles negatives and gaps).
- 2Iterate from the right end. For nums[i] with rank r, query prefix(r − 1) — the count of smaller values inserted so far.
- 3Record that count, then add rank r into the tree with weight 1.
- 4Reverse nothing — you filled results[i] directly.
Key insight
Turning "count smaller to the right" into "prefix frequency query over values seen so far" converts an O(n²) scan into O(n log n) — the same skeleton counts inversions.
The solution
Watch out for
- Query prefix(rank − 1), not prefix(rank) — "strictly smaller" excludes equal values.
- Merge-sort-with-counting is an equally valid O(n log n) alternative interviewers accept.