Policy-Based Data Structures

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):

  1. find_by_order(k): It returns the iterator pointing towards the kth largest element(starting from 0).

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.

The girl who loves to code | Software Developer | Follow me at: https://salonix.netlify.app