Find no of reverse pairs in an array which is sorted in two parts in O(N)

Objective: Given an array of integers A[] which is sorted in two parts (both parts are individually sorted), find no of reverse pairs means no of (i, j) pairs where i belongs to the part one and j belongs to part 2 and A[i]>A[j].

Example:

A[] = {4, 6, 8, 9, 1, 5, 10, 11}

Output:  7
Explanation:
Part one: {4, 6, 8, 9}
Part two: {1, 5, 10, 11}
Reversed pairs: (4, 1) (6, 1) (6, 5) (8, 1) (8, 5) (9, 1) (9, 5) = 7

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:

  • Iterate the array and find the start index of second sorted array part say it is m.
  • Part one if from 0 to m-1. Part two is from m to length-1.
  • Take two pointer (i and j), i at the index 0 (start index of part one) and j at the

Pseudo code:

Initialize result = 0.
Do while i<=m-1 && j<=length-1.
     If A[i]>A[j] then
        result = result + (m-i)+1.
     do j++.
     If A[i]<=A[j] do i++;
End Loop

Time Complexity: O(N)

Example:

A[] = {4, 6, 8, 9, 1, 5, 10, 11}
i = 0, end_partone = 3, j = 4, end_part_two=7, result =0
A[i]>A[j] (4>1), result = result + end_partone – i+1 => 0+3-0+1 = 4
j++

i = 0, end_partone = 3, j = 5, end_part_two=7, result =4
A[i]>A[j] (4<5) => i++ => i=1

i = 1, end_partone = 3, j = 5, end_part_two=7, result =4
A[i]>A[j] (6>5), result = result + end_partone – i+1 => 4+3-1+1 = 7
j++

i = 1, end_partone = 3, j = 6, end_part_two=7, result =7
A[i]>A[j] (6<10) => i++ => i=2

i = 2, end_partone = 3, j = 6, end_part_two=7, result =7
A[i]>A[j] (8<10) => i++ => i=3

i = 3, end_partone = 3, j = 6, end_part_two=7,  result =7
A[i]>A[j] (9<10) => i++ => i=4  (break)

Code:



Output:

No of reversed pair: 15

__________________________________________________
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.
__________________________________________________

  • lipsa patel

    In the Pseudo code,
    “result = result + (m-1)-i.”

    should be

    result = result + (m-i)+1;

    • tutorialhorizon

      Thanks Lipsa. Yet again you have found the problem. We have corrected it.

%d bloggers like this: