Find Number of reverse pairs in an array

Objective: Given an array of integers A[],find no of reverse pairs means no of (i, j) pairs where i < j and A[i]>A[j].

Example:

A[] = {10,
3, 4, 2, 5, 7, 9, 11}

Output:7
Reversed pairs: (10, 3) (10, 4) (10, 2) (10, 5) (10, 7) (10, 9) (3, 2) (4, 2) = 8

Approach:

Naïve Approach:

Use nested for loops and compare each element with all other elements in array and check if it is reversed pair, if yes then add it to the result. At the end print the result.

Time Complexity: O(N2)

Better Approach: Divide and Conquer

Earlier we have seen the similar problem where array is sorted in two parts and we solved it O(N) time. We recommend to read the following article before continue.

Steps:

  • Divide the array into 2 parts.
  • Sort both the parts.
  • Find reverse pairs in both parts, add them to result and then merge both the parts. (This step is important, make sure you find the reverse pairs first before you sort them because sorting will change the order).
  • We can find the reverse pairs in O(N)time as we have done in this article – Find no of reverse pairs in an array sorted in two parts.
  • You might think that sorting will change the order of the array then result will be wrong for finding reverse pairs but here the trick is we are finding the reverse pairs before we sort let’s take one example.

Example:

{10, 3, 4, 2}

Divide –
{10, 3} and {4, 2}

Divide –
{10} {3} {4} {4}

find the reverse pair in {10}  {3} arrays
Reverse pair
= (10, 3) , now sort it then merge it, new array will be {3, 10} 

find the reverse pair in {4}  {2} arrays
Reverse pair
= (4, 2) , now sort it then merge it, new array will be {2, 4} 

find the reverse pair in {3, 10}  {2, 4} arrays –Now if you notice order of 3, 10 is changed but still it will not affect the result since pair (10, 3) is already found and further pairs which we will find for them 10 and 3 will be on the left side.

See the image below for full example –

Code:

Output:

No of reversed pair: 8

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: