Are you facing difficulties in solving Inversion Count related coding problems? Then my Today’s blog is for you! Keep reading :)
First, let me give a brief intro. Inversion Count for an array indicates — how far (or close) the array is from being sorted. If the array is already sorted then the Inversion count is 0.Let us take an example of an array, arr = {8, 4, 2, 1}. Given array has six inversions:
(8,4), (4,2), (8,2), (8,1), (4,1), (2,1). This means two elements form an inversion if i<j and a[i]>a[j]. So the basic approach that you will be thinking would be using Merge Sort, but the good thing is we can easily do this in C++ using Policy-Based Data Structures(PBDS). The PBDS provides the programmer a high-performance, semantic safety and flexibility as compared to the standard data structures of the C++ std library.
It works similarly as Sets. It has two other functionalities which make it better (which is going to solve our Inversion count problem):
- find_by_order(k): It returns the iterator pointing towards the kth largest element(starting from 0).
- order_of_key(k): It returns the number of elements in the set which are strictly less than K.This will take O(log(n)) time complexity.
So, by using find_by_order(k) functionality, iterate over each element in the array, and also, insert it in a stack. It will give the number of elements strictly less than K.But we want, a number of elements greater than K, so subtract find_by_order(i) from present stack size. Hence you will get the inversion count.
To know more about PBDS, Refer to this.
