Reverse Pairs

Hard
0/120
Average time to solve is 50m
profile
Contributed by
114 upvotes
Asked in companies
IBMMongoDBD.E.Shaw

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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
Sample Input 1 :
1
6
1 2 3 2 3 1
Sample Output 1 :
2
Explanation Of Sample Input 1 :
Test case 1: 
Given that we follow 1-based indexing, for the array {1, 2, 3, 2, 1}, the pairs satisfying the conditions of Reverse Pairs are 
For i = 3, arr[i] = 3 and for j = 6, arr[j] = 1.
For i = 5, arr[i] = 3 and for j = 6, arr[j] = 1.
Hence there are two possible pairs.
Sample Input 2 :
2
6
6 4 8 2 1 3
5
2 4 3 5 1
Sample Output 2 :
6
3
Explanation Of Sample Input 2 :
Test case 1: 
Given that we follow 1-based indexing,The possible pairs satisfying the conditions of Reverse Pairs are (1, 4), (1, 5), (2, 5), (3, 4), (3, 5), (3, 6). Thus, the answer is 6.

Test case 2: 
Given that we follow 1-based indexing, The possible pair of indices satisfying the above condition are (2, 5), (3, 5), (4, 5). Thus, the answer is 3.
Hint

Can you think about the simplest possible solution?

Approaches (2)
Brute-Force
  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.
Time Complexity

O(N ^ 2), Where N is the number of elements in the given array/list.

 

Since we are considering every index j for given index i, such that j > i, we will have (N * (N - 1)) / 2 pairs to consider. Hence the overall complexity will be O(N ^ 2).

Space Complexity

O(1).

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Reverse Pairs
Full screen
Console