How many are smaller to the right
For every position of an array, count the smaller values to its right, by scanning from the right and keeping a structure that counts how many seen values are below a given value. About 26 minutes.
Ask, then add
Comparing each value with everything to its right takes up to n squared steps. Flip the work. Scan from the right end. When you reach a value, the values you have already scanned are exactly those to its right.
So ask: how many of the scanned values are smaller than this one? That is its answer. Then add the value to the scanned set.
less = count_below(x) # ask first add(x) # then add
Start from the right. 2 has nothing to its right: 0. Add 2 to the set.
Counting by rank
You need a structure that supports two things quickly: add a value, and count the stored values below a given one. A search tree in which every node stores how many nodes are in its left part does this. So does a Fenwick tree, an array that keeps partial counts.
Replace each value by its rank among the distinct values, so that ranks run from 1 up to the number of distinct values. Then a Fenwick tree over the ranks answers each question in about log n steps.
i = 5 i += i & -i # 6: the next block
Why scan from the right?
- AThe values already scanned are exactly the ones to the right of the current value
- BThe right end is quicker to reach
- CThe array is sorted from the right
Show the answer
The values already scanned are exactly the ones to the right of the current value. So counting the smaller scanned values answers the question.
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].
nums = [5, 2, 6, 1] → [2, 1, 1, 0]
1 ≤ length of nums ≤ 3,000 · -10,000 ≤ nums[i] ≤ 10,000