Count number of Inversions in an array - The Coding Shala
In this post, we will how to Count the number of Inversions in an array and will implement its solution in Java.
Count number of Inversions in an array
Count number of Inversions in an array Java Program
Point to Remember: There are two types of inversion: Global and local inversions. The Global inversions are the number of i<j and A[i]>A[j]. The local inversions is the number of i with 0<=i<N(size) and A[i]>A[i+1]. So we can say all local inversions are global inversions.
Here we need to find the total number of global inversions.
Using Brute Force. We can simply check using two loops.
Time Complexity will be O(N^2).
Using sorting Algorithms.
Here we are going to use Merge Sorting Algorithm. Why Merge Sorting? Merge Sorting Algorithm takes O(n log n) time in the average case. Other Algorithm normally takes O(n^2) time.
Merge sorting algorithm works based on divide and conquer.
So the idea here is to implement the merge sort algorithm as we do normally. We divide our array into two parts: left and right part. These left part and right parts are sorted then we merge them back. We know that if an element in the left part is greater than an element in the right part of the array then all the elements in the left parts after the current element are greater than the right part element so we add all the elements of the left part after the current left part element to the count. Because all these elements make an inversion.
let's understand this by an example:
in next step we see 2 is greater than 1 so after 2 every element in left part will be greater than 1 so we add left_length-left_index to the count.
Time Complexity = O(n log n).
- Sort an array according to the count of set bits
- find the first duplicate in an array
- Intersection of two arrays
- Median of two sorted arrays
- Max Non-Negative subarray