Problem Overview & Intuition

A reverse pair requires nums[i] > 2 * nums[j] with i < j. Using Divide and Conquer (Merge Sort), because both left and right subarrays are sorted, for each left element we can advance a pointer in the right subarray monotonically in O(N) time per level.

Step-by-Step Approach

1. Divide nums recursively using merge sort.
2. Count reverse pairs between the sorted halves before merging: loop i in left, advance rightPtr while nums[i] > 2 * nums[rightPtr].
3. Merge the two sorted halves.
4. Return total reverse pairs.

Optimal Implementation (JavaScript)

function reversePairs(nums) {
  function mergeSort(left, right) {
    if (left >= right) return 0;
    const mid = Math.floor((left + right) / 2);
    let count = mergeSort(left, mid) + mergeSort(mid + 1, right);
    count += countPairs(left, mid, right);
    merge(left, mid, right);
    return count;
  }
  function countPairs(left, mid, right) {
    let count = 0, rightPtr = mid + 1;
    for (let i = left; i <= mid; i++) {
      while (rightPtr <= right && nums[i] > 2 * nums[rightPtr]) rightPtr++;
      count += (rightPtr - (mid + 1));
    }
    return count;
  }
  function merge(left, mid, right) {
    const temp = [];
    let i = left, j = mid + 1;
    while (i <= mid && j <= right) {
      if (nums[i] <= nums[j]) temp.push(nums[i++]);
      else temp.push(nums[j++]);
    }
    while (i <= mid) temp.push(nums[i++]);
    while (j <= right) temp.push(nums[j++]);
    for (let p = 0; p < temp.length; p++) nums[left + p] = temp[p];
  }
  return mergeSort(0, nums.length - 1);
}

Complexity Analysis