Reverse Pairs

Posted: 29 Jan, 2021
Difficulty: Hard


Try Problem

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
Approach 1
  1. The simplest possible solution to this problem is to apply brute force and find the pairs which satisfy the required conditions.
  2. We can use two nested loops, one for index ‘i’ and another for index ‘j’, so that we can compare all the pairs.
  3. Let variable count store the number of Reverse Pairs.
  4. Now, the algorithm will be as follows :
    1. L1: For i = 1 to N, considering all the indices of the array.
    2. L2: For j = i + 1 to N, considering all the indices greater than i.
      1. Since we already know that i < j, we can check if ARR[i] > 2 * ARR[j] satisfies:
        1. increment count by 1, i.e. count = count + 1.
  5. Finally, return the count.
    Note that L1 and L2 are two nested loops.
Try Problem