Last Updated: 29 Jan, 2021
Reverse Pairs
Hard
Asked in companies
You are given an array/list say ‘ARR’ of size ‘N’. We call pair (i, j) a Reverse Pair when i < j and 'ARR[i]' > 2 * 'ARR[j]'.
Your task is to find the number of Reverse Pairs present in given 'ARR'.
For example :
For the array [50, 21, 9], if we follow 1-based indexing, the Reverse Pairs are (1, 2), (1, 3) and (2, 3). Thus, the total count i.e. the answer becomes 3.
Note :
A single index of the pair (i, j) can be used multiple times.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of every test case contains an integer ‘N’ denoting the size of the array/list.
The second line of every test case contains ‘N’ space-separated integers denoting the elements of array/list 'ARR'.
Output Format :
For each test case, print the number of distinct pairs.
The output of each test case will be printed in a separate line.
Note :
You don’t have to print anything, it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 5
2 <= N <= 3000
1 <= ARR[i] <= 10^5
Where 'ARR[i]' denotes the i-th elements in the array/list.
Time Limit: 1 sec
Approaches
- The simplest possible solution to this problem is to apply brute force and find the pairs which satisfy the required conditions.
- We can use two nested loops, one for index ‘i’ and another for index ‘j’, so that we can compare all the pairs.
- Let variable count store the number of Reverse Pairs.
- Now, the algorithm will be as follows :
- L1: For i = 1 to N, considering all the indices of the array.
- L2: For j = i + 1 to N, considering all the indices greater than i.
- Since we already know that i < j, we can check if ARR[i] > 2 * ARR[j] satisfies:
- increment count by 1, i.e. count = count + 1.
- Since we already know that i < j, we can check if ARR[i] > 2 * ARR[j] satisfies:
- Finally, return the count.
Note that L1 and L2 are two nested loops.
- Since the previous approach was very inefficient for large values of N, we can use some kind of modified merge sort to solve this problem.
- Since merge sort works on divide and conquer paradigm, so, first we divide the array into smaller sorted arrays and merge them to form a completely sorted array.
- We can count the number of pairs which satisfies the above conditions while merging the array.
- Let mergeSort() be a recursive integer function which takes the array, starting pointer ‘S’ which points to the start of array and ending pointer ‘E’, which points to the end of the array which we are considering.
- mergeSort(), after processing the array, will return the count of the pairs which will satisfy the above conditions.
- In each round we try to divide the array into two parts and sort them.
- Look at the code below for better understanding of mergeSort:
- Consider the array {6, 4, 8, 2, 1, 3}. After running mergeSort we will have, leftPart = {4, 6, 8} and rightPart = {1, 2, 3}.
- Let i points to leftPart and j points to rightPart.
- So now we can just use two pointers two traverse the left and right parts. For each leftPart[i], if j <= E and arr[i] / 2 > arr[j], we just continue to move j to the end, to increase rightPart until it is valid.
- So leftPart’s 4 can match 1 and 2, leftPart’s 6 can match 1, 2, 3 and leftPart’s 8 can match 1, 2, 3. So in this particular iteration we will have 8 pairs and hence we can increment the total count by 8.
- Now we can just merge the left and right parts using an helper array and then again recursively find the count of merged arrays, until the base condition is reached.
- The pictorial representation for Divide algorithm is:
The pictorial representation for Conquer algorithm is:
For explanation of merge function:
Thus, the answer is 3 and indices pairs are (2, 4), (1, 3) and (1, 4).
Similar problems