Daily bit(e) of C++ | Count smaller elements after
Daily bit(e) of C++ #266, Common interview problem: Count smaller elements after.
Today, we will look at a common C++ interview problem: Count smaller elements after.
Given an array of integers "values" as std::vector<int>, return an array "counts", where counts[i] represents the number of elements smaller than values[i] to the right of values[i] (i.e. values[j] where j>i).
For example, for the values {5,1,4,2,6,7,3}, the count array is {4,0,2,0,1,1,0}.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/seGx61cnE.
Solution
Coming up with an efficient solution for this problem can be tricky. However, if we reformulate it slightly:
“If we would sort the values array, how many smaller elements would be ordered before values[i] compared to how many are ordered before values[i] now?”
The difference is the answer we are looking for. And because this re-ordering would happen during a sort, why not use a sort and appropriately instrument it to track this number?
Notably, merge sort is quite useful for this purpose. In merge sort, we always merge two already sorted (and adjacent) sub-arrays. This means that a high value can only be jumped-over by smaller values if it is in the left sub-array and only by values from the right sub-array.
Example: {1,4,7},{2,3,8}, merges into {1,2,3,4,7,8} where 4 and 7 were jumped over by two values (2 and 3).
The only complication remaining is that we need an indirect sort (over indexes), so that we can correctly track the number of times each element was jumped over in a separate array.
