Reverse Pairs Hard 0 attempts
LeetCode ↗

Reverse Pairs

Hard ArrayTwo Pointers LeetCode

You're given an integer array nums. Count how many index pairs (i, j) satisfy 0 <= i < j < nums.length and nums[i] > 2 * nums[j] — each such pair is called a reverse pair. Return the total count.

Input Format
Implement reversePairs(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
nums = [1,3,2,3,1]
Output
2

Example 2

Input
nums = [-5,-5]
Output
1
Constraints
  • 1 <= nums.length <= 5 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
Test Cases (2)
Case 1
Args: [[1,3,2,3,1]] Expected: 2
Case 2
Args: [[-5,-5]] Expected: 1
Topics
ArrayTwo Pointers

Use a modified merge sort. During the merge step, for each element in the left half, count how many elements in the right half satisfy nums[i] > 2 * nums[j] before performing the standard merge.

javascript
function reversePairs(nums) {
  let count = 0;

  function mergeSort(arr, lo, hi) {
    if (lo >= hi) return;
    const mid = (lo + hi) >> 1;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);

    let j = mid + 1;
    for (let i = lo; i <= mid; i++) {
      while (j <= hi && arr[i] > 2 * arr[j]) j++;
      count += j - (mid + 1);
    }

    const temp = [];
    let l = lo, r = mid + 1;
    while (l <= mid && r <= hi) {
      if (arr[l] <= arr[r]) temp.push(arr[l++]);
      else temp.push(arr[r++]);
    }
    while (l <= mid) temp.push(arr[l++]);
    while (r <= hi) temp.push(arr[r++]);
    for (let i = lo; i <= hi; i++) arr[i] = temp[i - lo];
  }

  mergeSort(nums, 0, nums.length - 1);
  return count;
}

Time: O(n log n) Space: O(n)

Saved in this browser only. Private to you.

JavaScript