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])
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 ( ).

Was this useful? If you’re interested, you can read more about more such puzzles for Tech Interviews ( )or you can take do some online programming challenges ( )

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