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].

Examples

Example 1:

1
2

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

Example 2:

1
2

Input: nums = [2,4,3,5,1]
Output: 3

Solution

Method 1 - Using sorting

To solve this efficiently, we employ a modified merge sort algorithm. During the merge step of merge sort, we count reverse pairs across the two halves (left and right).

Steps

  1. Divide and Conquer: Split the array into two halves recursively until they consist of a single element.
  2. Count Reverse Pairs: During the merge step, before merging the two halves, we count the reverse pairs (i, j) where:
    • nums[i] > 2 * nums[j] and i is in the left half while j is in the right half.
  3. Merge: Merge the two halves in sorted order to maintain the sorting for subsequent merge steps.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] arr, int start, int end) {
        if (start >= end) {
            return 0;
        }

        int mid = (start + end) / 2;
        int ans = mergeSort(arr, start, mid) + mergeSort(arr, mid + 1, end);

        // Count reverse pairs
        int j = mid + 1;
        for (int i = start; i <= mid; i++) {
            while (j <= end && arr[i] > 2L * arr[j]) {
                j++;
            }
            ans += j - (mid + 1);
        }

        // Merge step
        int[] temp = new int[end - start + 1];
        int l = start, r = mid + 1, k = 0;
        while (l <= mid && r <= end) {
            if (arr[l] <= arr[r]) {
                temp[k++] = arr[l++];
            } else {
                temp[k++] = arr[r++];
            }
        }
        while (l <= mid) {
            temp[k++] = arr[l++];
        }
        while (r <= end) {
            temp[k++] = arr[r++];
        }
        
        System.arraycopy(temp, 0, arr, start, end - start + 1);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge_sort(arr: List[int], start: int, end: int) -> int:
            if start >= end:
                return 0
            
            mid = (start + end) // 2
            ans = merge_sort(arr, start, mid) + merge_sort(arr, mid + 1, end)
            
            # Count reverse pairs
            j = mid + 1
            for i in range(start, mid + 1):
                while j <= end and arr[i] > 2 * arr[j]:
                    j += 1
                ans += j - (mid + 1)
            
            # Merge step
            temp = []
            l, r = start, mid + 1
            while l <= mid and r <= end:
                if arr[l] <= arr[r]:
                    temp.append(arr[l])
                    l += 1
                else:
                    temp.append(arr[r])
                    r += 1
            
            temp.extend(arr[l:mid + 1])
            temp.extend(arr[r:end + 1])
            arr[start:end + 1] = temp
            
            return ans
        
        return merge_sort(nums, 0, len(nums) - 1)

Complexity

  • ⏰ Time complexity: O(n log n). Dividing the array takes log n layers, and each merge step runs in O(n) for counting and merging.
  • 🧺 Space complexity: O(n). Temporary arrays are used during the merge step.