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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class ReversePairs { | |
| public static void findPairs(int [] A){ | |
| int len = A.length–1; | |
| //find the start index of part two sorted array | |
| int m=0; | |
| for (int i = 0; i <len ; i++) { | |
| if(A[i]>A[i+1]){ | |
| m=i+1; | |
| break; | |
| } | |
| } | |
| //initialize result | |
| int result = 0; | |
| //part one | |
| int start_partOne = 0; | |
| int end_partOne = m–1; | |
| //part two | |
| int start_partTwo = m; | |
| int end_partTwo = len–1; | |
| //take two pointers, at the beginning of both parts | |
| int i = start_partOne; | |
| int j = start_partTwo; | |
| while(i<=end_partOne && j<=end_partTwo){ | |
| if (A[i]<=A[j]) | |
| i++; | |
| else if(A[i]>A[j]){ | |
| result+=end_partOne–i+1; | |
| j++; | |
| } | |
| } | |
| System.out.println("No of reversed pair: " + result); | |
| } | |
| public static void main(String[] args) { | |
| int [] A = {4, 6, 8, 9, 0, 1, 2, 5, 10, 11}; | |
| findPairs(A); | |
| } | |
| } |
Output:
No of reversed pair: 15
In the Pseudo code,
“result = result + (m-1)-i.”
should be
result = result + (m-i)+1;
Thanks Lipsa. Yet again you have found the problem. We have corrected it.