# Reverse Pairs
**Difficulty:** HARD
[External](https://leetcode.com/problems/reverse-pairs)
Canonical: https://scaleengineer.com/dsa/problems/reverse-pairs
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Merge Sort](https://scaleengineer.com/algorithms/merge-sort)
**Data structures:** Array, Binary Indexed Tree, Segment Tree, Ordered Set
---
## Problem
Given an integer array `nums`, return _the number of **reverse pairs** in the array_.

A **reverse pair** is a pair `(i, j)` where:

* `0 <= i < j < nums.length` and
* `nums[i] > 2 * nums[j]`.

**Example 1:**

**Input:** nums = [1,3,2,3,1]
**Output:** 2
**Explanation:** The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

**Example 2:**

**Input:** nums = [2,4,3,5,1]
**Output:** 3
**Explanation:** The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

**Constraints:**

* `1 <= nums.length <= 5 * 104`
* `-231 <= nums[i] <= 231 - 1`

# Approaches
## Brute Force
This is the most straightforward approach, which involves checking every possible pair of indices `(i, j)` where `i < j` and testing if they satisfy the reverse pair condition.
**Time:** O(N^2), where N is the number of elements in the array. The two nested loops result in a quadratic number of pair comparisons. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop indices.
**Pros:** Very simple to understand and implement.; Requires no extra space apart from a few variables for loops and the counter.
**Cons:** Highly inefficient for large arrays. It will result in a "Time Limit Exceeded" (TLE) error for the given constraints (`N <= 5 * 10^4`).
### Explanation
The algorithm iterates through all possible pairs of elements in the array. For each element `nums[i]`, it scans the rest of the array to its right (elements `nums[j]` where `j > i`). For each such pair, it checks if `nums[i]` is greater than `2 * nums[j]`. A counter is used to keep track of how many such pairs are found. To avoid potential integer overflow when calculating `2 * nums[j]` (since `nums[j]` can be large), it's crucial to cast the numbers to a 64-bit integer type (`long` in Java) before performing the multiplication and comparison.

```java
class Solution {
    public int reversePairs(int[] nums) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((long) nums[i] > 2 * (long) nums[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use two nested loops. The outer loop iterates with index `i` from `0` to `n-1`.
- The inner loop iterates with index `j` from `i + 1` to `n-1`.
- Inside the inner loop, check if the condition `(long)nums[i] > 2 * (long)nums[j]` is met. Casting to `long` is important to prevent integer overflow.
- If the condition is true, increment the `count`.
- After the loops complete, return the final `count`.

## Divide and Conquer using Merge Sort
A much more efficient approach is to use a divide-and-conquer strategy, specifically by modifying the Merge Sort algorithm. The core idea is that while merging two sorted subarrays, we can efficiently count the reverse pairs that span across these two halves.
**Time:** O(N log N). The algorithm's recurrence relation is T(N) = 2T(N/2) + O(N), which solves to O(N log N). The O(N) part comes from the linear-time scan for counting pairs and the linear-time merge operation at each level of recursion. · **Space:** O(N), due to the temporary array required for the merge step of the algorithm. The recursion depth adds O(log N) to the call stack, but the O(N) space for the merge buffer dominates.
**Pros:** Highly efficient and optimal, passing the time limits for large inputs.; It is a classic and elegant application of the divide-and-conquer paradigm.
**Cons:** More complex to implement and reason about compared to the brute-force approach.; It either modifies the input array or requires an auxiliary array of the same size.
### Explanation
This algorithm recursively splits the array into two halves until we have subarrays of size 1. Then, as it merges the subarrays back, it counts the reverse pairs. The total count is the sum of reverse pairs within the left half, within the right half, and across the two halves.

The crucial part is counting the pairs `(i, j)` where `i` is in the left sorted half and `j` is in the right sorted half. Since both halves are sorted, we can do this in linear time. We use two pointers. For each element `nums[i]` in the left half, we find the number of elements `nums[j]` in the right half that satisfy `nums[i] > 2 * nums[j]`. Because the arrays are sorted, we can find these counts efficiently without re-scanning the right half for every element of the left half. After counting, the two halves are merged to maintain the sorted order for the upper levels of recursion.

```java
class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int low, int high) {
        if (low >= high) {
            return 0;
        }
        int mid = low + (high - low) / 2;
        int count = mergeSort(nums, low, mid) + mergeSort(nums, mid + 1, high);
        
        // Count reverse pairs where one element is in the left half and the other in the right
        int j = mid + 1;
        for (int i = low; i <= mid; i++) {
            while (j <= high && (long)nums[i] > 2L * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }
        
        // Merge the two sorted halves
        merge(nums, low, mid, high);
        
        return count;
    }

    private void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low, j = mid + 1, k = 0;
        while (i <= mid && j <= high) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= high) {
            temp[k++] = nums[j++];
        }
        for (int l = 0; l < temp.length; l++) {
            nums[low + l] = temp[l];
        }
    }
}
```
### Algorithm
- Define a recursive function `mergeSortAndCount(nums, low, high)`.
- **Base Case:** If `low >= high`, it means the subarray has 0 or 1 element, so return 0.
- **Divide:** Find the middle index `mid = low + (high - low) / 2`.
- **Conquer:** Recursively call the function for the left half (`low` to `mid`) and the right half (`mid + 1` to `high`). Sum their results: `count = mergeSortAndCount(nums, low, mid) + mergeSortAndCount(nums, mid + 1, high)`.
- **Combine & Count:**
  - This is the key step. Both halves `nums[low...mid]` and `nums[mid+1...high]` are now sorted.
  - Count pairs `(i, j)` where `i` is in the left half and `j` is in the right. Use two pointers: `i` for the left half and `j` for the right.
  - For each `i` from `low` to `mid`, advance `j` in the right half as long as `(long)nums[i] > 2L * nums[j]`. The number of such `j`'s found is `j - (mid + 1)`. Add this to `count`.
  - Since both subarrays are sorted, the `j` pointer does not need to be reset for each `i`, making this counting step O(N).
- **Merge:** Perform a standard merge operation to combine the two sorted halves into a single sorted array. This is crucial for the correctness of the parent recursive calls.
- Return the total `count`.

# Solutions
### Java

```java
class Solution {
public
  int reversePairs(int[] nums) {
    TreeSet<Long> ts = new TreeSet<>();
    for (int num : nums) {
      ts.add((long)num);
      ts.add((long)num * 2);
    }
    Map<Long, Integer> m = new HashMap<>();
    int idx = 0;
    for (long num : ts) {
      m.put(num, ++idx);
    }
    BinaryIndexedTree tree = new BinaryIndexedTree(m.size());
    int ans = 0;
    for (int i = nums.length - 1; i >= 0; --i) {
      int x = m.get((long)nums[i]);
      ans += tree.query(x - 1);
      tree.update(m.get((long)nums[i] * 2), 1);
    }
    return ans;
  }
} class BinaryIndexedTree {
private
  int n;
private
  int[] c;
public
  BinaryIndexedTree(int n) {
    this.n = n;
    c = new int[n + 1];
  }
public
  void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += lowbit(x);
    }
  }
public
  int query(int x) {
    int s = 0;
    while (x > 0) {
      s += c[x];
      x -= lowbit(x);
    }
    return s;
  }
public
  static int lowbit(int x) { return x & -x; }
}

```

### CPP

```cpp
class BinaryIndexedTree { public: int n ; vector < int > c ; BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += lowbit ( x ); } } int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= lowbit ( x ); } return s ; } int lowbit ( int x ) { return x & - x ; } }; class Solution { public: int reversePairs ( vector < int >& nums ) { set < long long > s ; for ( int num : nums ) { s . insert ( num ); s . insert ( num * 2ll ); } unordered_map < long long , int > m ; int idx = 0 ; for ( long long num : s ) m [ num ] = ++ idx ; BinaryIndexedTree * tree = new BinaryIndexedTree ( m . size ()); int ans = 0 ; for ( int i = nums . size () - 1 ; i >= 0 ; -- i ) { ans += tree -> query ( m [ nums [ i ]] - 1 ); tree -> update ( m [ nums [ i ] * 2ll ], 1 ); } return ans ; } };
```

### Python

```python
class BinaryIndexedTree : def __init__ ( self , n ): self . n = n self . c = [ 0 ] * ( n + 1 ) @ staticmethod def lowbit ( x ): return x & - x def update ( self , x , delta ): while x <= self . n : self . c [ x ] += delta x += BinaryIndexedTree . lowbit ( x ) def query ( self , x ): s = 0 while x > 0 : s += self . c [ x ] x -= BinaryIndexedTree . lowbit ( x ) return s class Solution : def reversePairs ( self , nums : List [ int ]) -> int : s = set () for num in nums : s . add ( num ) s . add ( num * 2 ) alls = sorted ( s ) m = { v : i for i , v in enumerate ( alls , 1 )} ans = 0 tree = BinaryIndexedTree ( len ( m )) for num in nums [:: - 1 ]: ans += tree . query ( m [ num ] - 1 ) tree . update ( m [ num * 2 ], 1 ) return ans
```