Last Updated: 10 Jan, 2017
Count Inversions
Moderate
Asked in companies
For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist.
An inversion is defined for a pair of integers in the array/list when the following two conditions are met.
A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when:
1. 'ARR[i] > 'ARR[j]'
2. 'i' < 'j'
Where 'i' and 'j' denote the indices ranging from [0, 'N').
Input format :
The first line of input contains an integer 'N', denoting the size of the array.
The second line of input contains 'N' integers separated by a single space, denoting the elements of the array 'ARR'.
Output format :
Print a single line containing a single integer that denotes the total count of inversions in the input array.
Note:
You are not required to print anything, it has been already taken care of. Just implement the given function.
Constraints :
1 <= N <= 10^5
1 <= ARR[i] <= 10^9
Where 'ARR[i]' denotes the array element at 'ith' index.
Time Limit: 1 sec
Approaches
The steps are as follows:
- Initialize a ‘COUNT’ with 0 to keep track of the number of inversions
- Iterate over every element in the array in a linear fashion starting from 0.
- For every element, check all the elements ahead of the current element and check the condition.
- If the condition satisfies, increase the ‘COUNT’ by 1.
- Otherwise, move to the next iteration.
- Return the ‘COUNT’.
The steps are as follows:
- The idea is similar to merge sort, divide the array from the middle to two parts, say, left sub-array and right sub-array.
- Write a logic that counts the number of inversions when the arrays, namely, left sub-array and right sub-array are merged. The idea is to have two indices or pointers. One of the pointers will refer to the left sub-array and the other one will point to the right sub-array. Let’s call them ‘LEFTINDEX’ and ‘RIGHTINDEX’ such that:
- ‘LEFTINDEX' < ‘RIGHTINDEX’ and
- 'LEFTSUBARRAY[LEFTINDEX]' > 'RIGHTSUBARRAY[RIGHTINDEX]'
- We can deduce major information from this configuration. We can say, there would be ('MID' - ‘LEFTINDEX’) inversions, where ‘MID’ is the index from where the array has been split into two. (We can say so because all the remaining elements in the left-subarray ('LEFTSUBARRAY[LEFTINDEX+ 1]', ‘LEFTSUBARRAY[LEFTINDEX+ 2]’ ….. ‘LEFTSUBARRAY[MID]’) will be greater than ‘RIGHTSUBARRAY[RIGHTINDEX]’)
- Extend the same idea to calculate the number of inversions in the left sub-array and right sub-array.
In this approach, we will create a Fenwick tree with every element having value 0 and map the given array to get the position of every element according to sorted order and then iterate through the positions and update the Fenwick tree to 1 for every element.
The steps are as follows:
- In the Main Function:
- Create an array “mask” in which we will store every element in the form of permutation of numbers from 1 to n having the same relative order of every element as of the original array.
- For example, if your original array is {3, 22, 11, 5} then your “masked” array must be like {1, 4, 3, 2}.
- Create an array “fenwick” of size ‘n’ and initialize it to zero. Denoting that we have not encountered any element from the array and as we encounter that element we will update it to 1 by “fenwickUpdate” function.
- Take a variable “answer” to store the final answer.
- Now iterate through the array “mask” from 0 to n-1(say iterator be i):
- Call the function “fenwickSum(mask[i], fenwick)” and add the value returned by this function to “answer”.
- Now call the function “fenwickUpdate(mask[i], mask.size(), fenwick).
- Return “answer”.
- In the “fenwickSum” function:
- This function will help us to sum all the elements which are greater than the current element but have an index lower than the current index.
- Take a variable “answer” in which we will keep count of those elements.
- “Index” will be the value that was passed to this function in our case it is “mask[i]”.
- While “index” is greater than 0:
- Add “fenwick[index]” to “answer”.
- Update “index” to “index” - (“index” & (- “index”)).
- Return “Sum”.
- In the “fenwickUpdate” function:
- In this function, we will update the values of elements that have been visited to be 1.
- Take a while loop till “index” is less than size of array:
- Update “fenwick[index]” = 1.
- Update “index” to “index” + (“index” & (- “index”)).