Sign in to follow this  
CodeGround Online Testing

Count Inversions


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 )

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this