270. Count of Smaller Numbers After Self
You are given an integer array nums. For every position i, look only at the elements that come after it and count how many of them are strictly smaller than nums[i].
Return an integer array counts of the same length, where counts[i] is that number for position i. The last position always gets 0, since nothing comes after it.
The interesting part is doing this faster than comparing every pair.
Example 1:
Input: nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]
Explanation: After the 5 come 2 and 1 (two smaller values). After the 2 comes only the 1. After the 6 comes only the 1. Nothing follows the 1.
Example 2:
Input: nums = [-1, -1]
Output: [0, 0]
Explanation: The second -1 is equal to the first, not strictly smaller, so both counts are 0.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
- Only strictly smaller elements count — equal values do not.
Hints:
The pairwise check is easy to write but O(n²). To beat it, you need a structure that answers "how many of the values I've already processed are smaller than x?" quickly.
Sweep from right to left, keeping the elements seen so far in sorted order. A binary search (lower bound) for the current value tells you exactly how many of them are strictly smaller.
For a guaranteed O(n log n): count during merge sort. When merging, every time an element jumps from the right half to before an element of the left half, it was a smaller element that originally sat after it — sort *indices* so each left element can accumulate that jump count.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [5, 2, 6, 1]
Expected output: [2, 1, 1, 0]