Count of Smaller Numbers After Self hard
Description
Given nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are smaller than nums[i].
Examples
> nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]
# 5 -> {2,1} smaller on the right = 2
# 2 -> {1} = 1
# 6 -> {1} = 1
# 1 -> {} = 0Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Intuition — value-indexed BIT, right to left
Process the array right to left. Maintain a BIT indexed by value, where bit counts how many values you’ve already seen (i.e. that lie to the right of the current element). For each nums[i]:
- Query
prefixSum(value − 1)→ how many already-seen values are strictly smaller. That’scounts[i]. - Update
add(value, 1)→ record the current value for elements further left.
Because values can be negative and span a wide range, coordinate-compress them to ranks 1..k first.
Code
Query before you update, and use prefixSum(rank − 1) for “strictly smaller.” If you add the current value first, it would count itself. And querying prefixSum(rank) instead of rank − 1 would include equal values — the problem wants strictly smaller. Right-to-left order is what makes “already seen” mean “to the right.”
Intuition recap & alternative
This is the inversion-counting problem. A merge sort that counts inversions during the merge (Day 26) solves it equally well in O(n log n). The BIT version is often easier to reason about once you’ve seen the value-indexed pattern, and it generalizes to “count in a range.”
Analysis
- Time: O(n log n) — n elements, each an O(log k) query + update; plus O(n log n) to sort for compression.
- Space: O(n) for the BIT and the rank map.
Same skin
- Reverse Pairs — same BIT technique, with a
2 × nums[j]twist. - Count of Smaller (D&C version, Day 26) — the merge-sort approach to the identical problem.
- Queue Reconstruction by Height — another order-statistic BIT problem.