ChetanaSforum

# Count Inversions

## Recommended Posts

What is an inversion?
Let A be an array of n distinct numbers. If i < j and A > A[j], then the pair (i, j) is called an inversion of A.
For example, the array {2,3,8,6,1} has 5 inversions: (2,1) (3,1) (8,6) (8,1) and (6,1)
Trivial Solution to count the number of inversions in an array
countInversions = 0;
for i = 1 to N
for j = i+1 to N
if(A > A[j])
countInversions++;
The overall time complexity for this approach is O(n^2)
Using Merge Sort to count the number of inversions in O(n logn) time
The approach using Merge Sort to count the number of inversions is detailed in this blog post ( https://codeground.in/blog/index.php/2016/11/13/technical-interview-question-on-data-structure-and-algorithms-count-the-number-of-inversions-in-an-array/ ).

Was this useful? If you’re interested, you can read more about more such puzzles for Tech Interviews ( https://codeground.in/blog/index.php/category/interview-preparation/data-structures-algorithms-tech-interview-questions/ )or you can take do some online programming challenges ( https://codeground.in/screening-tests/coding-contests.html )