Reverse Pairs

Problem Statement

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
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 * 10⁴
-2³¹ ≤ nums[i] ≤ 2³¹ - 1

Approach 1: Brute Force

Explanation: Check all pairs (i, j) where i < j and count pairs where nums[i] > 2 * nums[j].

Time Complexity: O(n²)

Space Complexity: O(1)

function reversePairs(nums):
    count = 0
    n = length of nums
    
    for i = 0 to n-2:
        for j = i+1 to n-1:
            if nums[i] > 2 * nums[j]:
                count++
    
    return count

💡 Think: Simple nested loop checks all pairs but too slow for large inputs.

Approach 2: Merge Sort (Optimal)

Explanation: Use modified merge sort to count reverse pairs while sorting. During the merge step, count pairs where left[i] > 2 * right[j] before merging sorted halves.

Time Complexity: O(n log n)

Space Complexity: O(n) for auxiliary array

function reversePairs(nums):
    return mergeSort(nums, 0, length-1)

function mergeSort(nums, left, right):
    if left >= right:
        return 0
    
    mid = left + (right - left) / 2
    count = mergeSort(nums, left, mid) + mergeSort(nums, mid+1, right)
    
    // Count reverse pairs
    j = mid + 1
    for i = left to mid:
        while j <= right and nums[i] > 2 * nums[j]:
            j++
        count += (j - (mid + 1))
    
    // Merge sorted halves
    merge(nums, left, mid, right)
    return count

function merge(nums, left, mid, right):
    temp = empty array
    i = left, j = mid + 1
    
    while i <= mid and j <= right:
        if nums[i] <= nums[j]:
            temp.append(nums[i++])
        else:
            temp.append(nums[j++])
    
    while i <= mid:
        temp.append(nums[i++])
    while j <= right:
        temp.append(nums[j++])
    
    // Copy back to original array
    for k = left to right:
        nums[k] = temp[k - left]

💡 Think: Count pairs during merge sort's divide step, then merge sorted subarrays efficiently.

Approach 3: Binary Indexed Tree (BIT) / Fenwick Tree

Explanation: Use coordinate compression and BIT to efficiently count elements. For each element, query count of elements > 2*nums[i] seen so far, then insert current element.

Time Complexity: O(n log n)

Space Complexity: O(n)

function reversePairs(nums):
    // Coordinate compression
    sorted_nums = sorted(set of nums and 2*num for each num in nums)
    compress = map each value to its index in sorted_nums
    
    bit = BinaryIndexedTree of size len(sorted_nums)
    count = 0
    
    for i = length-1 down to 0:
        // Count elements > 2*nums[i]
        idx = compress[2 * nums[i]]
        count += bit.query(idx - 1)
        
        // Insert current element
        idx = compress[nums[i]]
        bit.update(idx, 1)
    
    return count

class BinaryIndexedTree:
    function update(index, delta):
        while index < size:
            tree[index] += delta
            index += index & (-index)
    
    function query(index):
        sum = 0
        while index > 0:
            sum += tree[index]
            index -= index & (-index)
        return sum

💡 Think: Compress coordinates, traverse right-to-left counting larger elements with BIT.

Approach 4: Segment Tree

Explanation: Similar to BIT but using segment tree for range sum queries. Coordinate compression maps values to indices, segment tree tracks count of each value seen.

Time Complexity: O(n log n)

Space Complexity: O(n)

// C++: Segment Tree (point update, range sum) + reversePairs using coordinate compression
class SegTree{
  vector<int> t;
public:
  SegTree(int n){ t.assign(4*n, 0); }

  int query(int ql, int qr, int idx, int l, int r){
    if(ql > r || qr < l) return 0;
    if(ql <= l && r <= qr) return t[idx];
    int mid=(l+r)/2;
    return query(ql,qr,2*idx+1,l,mid) + query(ql,qr,2*idx+2,mid+1,r);
  }

  void update(int pos, int val, int idx, int l, int r){
    if(l==r){ t[idx] += val; return; }
    int mid=(l+r)/2;
    if(pos <= mid) update(pos,val,2*idx+1,l,mid);
    else update(pos,val,2*idx+2,mid+1,r);
    t[idx]=t[2*idx+1] + t[2*idx+2];
  }
};

class Solution {
public:
  int reversePairs(vector<int>& nums){
    int n = nums.size();
    // coordinate compression of nums and 2*nums
    vector<long long> vals; vals.reserve(2*n);
    for(long long x: nums){ vals.push_back(x); vals.push_back(2LL*x); }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = vals.size();

    SegTree seg(m);
    long long ans = 0;
    for(int i=n-1;i>=0;--i){
      long long target = 2LL*nums[i];
      // first index strictly greater than target
      int pos = upper_bound(vals.begin(), vals.end(), target) - vals.begin();
      if(pos < m) ans += seg.query(pos, m-1, 0, 0, m-1);

      int idx = lower_bound(vals.begin(), vals.end(), (long long)nums[i]) - vals.begin();
      seg.update(idx, 1, 0, 0, m-1);
    }
    return (int)ans;
  }
};

💡 Think: Segment tree provides flexible range queries with coordinate compression for value mapping.

Solve on LeetCode