Code Implementation

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

class Solution {
public:
    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
        int j = mid + 1;
        for (int i = left; i <= mid; ++i) {
            while (j <= right && (long long)nums[i] > 2LL * nums[j]) j++;
            count += j - (mid + 1);
        }
        // Merge
        vector<int> temp;
        int l = left, r = mid + 1;
        while (l <= mid && r <= right) {
            if (nums[l] <= nums[r]) temp.push_back(nums[l++]);
            else temp.push_back(nums[r++]);
        }
        while (l <= mid) temp.push_back(nums[l++]);
        while (r <= right) temp.push_back(nums[r++]);
        for (int i = left; i <= right; ++i) nums[i] = temp[i - left];
        return count;
    }
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }
};
      

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }
    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long)nums[i] > 2 * (long)nums[j]) j++;
            count += j - (mid + 1);
        }
        // Merge
        int[] temp = new int[right - left + 1];
        int l = left, r = mid + 1, k = 0;
        while (l <= mid && r <= right) {
            if (nums[l] <= nums[r]) temp[k++] = nums[l++];
            else temp[k++] = nums[r++];
        }
        while (l <= mid) temp[k++] = nums[l++];
        while (r <= right) temp[k++] = nums[r++];
        for (int i = 0; i < temp.length; i++) nums[left + i] = temp[i];
        return count;
    }
}
      

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

Problem Description

Given an array of integers nums, count the number of reverse pairs in the array. A reverse pair is defined as a pair of indices (i, j) where i < j and nums[i] > 2 * nums[j].

• Each element in nums can be used only in its original position; you cannot reuse elements for different indices.
• The indices i and j must satisfy i < j.
• Your task is to return the total number of such pairs in the given array.

Constraints:

• 1 <= nums.length <= 5 * 10^4
• -2^{31} <= nums[i] <= 2^{31} - 1

Thought Process

The most direct approach is to check every possible pair (i, j) and count if nums[i] > 2 * nums[j]. This brute-force method is simple to implement but inefficient for large arrays because it checks every possible pair, leading to a time complexity of O(n²).

However, since the array can be quite large (up to 50,000 elements), a more efficient approach is needed. We notice that the problem is similar to counting inversions in an array, which can be efficiently solved using a modified merge sort. The key insight is that during the merge step, both halves are sorted, allowing us to count reverse pairs efficiently by using two pointers.

The optimized approach leverages the divide-and-conquer paradigm, splitting the array, counting reverse pairs in each half, and then counting pairs that span the two halves, all while sorting the array.

Solution Approach

• Step 1: Use Modified Merge Sort
  • Just like in inversion count, we use merge sort to recursively divide the array into halves.
• Step 2: Count Reverse Pairs During Merge
  • Before merging two sorted halves, for each element in the left half, we find how many elements in the right half satisfy nums[i] > 2 * nums[j].
  • Because both halves are sorted, we can use a pointer to efficiently find the rightmost j for each i.
• Step 3: Merge the Halves
  • After counting, merge the two halves into a sorted array so that the next level of merge sort works correctly.
• Step 4: Repeat Recursively
  • Apply the same logic recursively to all subarrays until the entire array is processed.

This approach ensures that each pair is counted exactly once, and the overall time complexity is reduced to O(n log n).

Example Walkthrough

Consider the input nums = [1, 3, 2, 3, 1].

• Divide into [1, 3, 2] and [3, 1]
• Further divide [1, 3, 2] into [1, 3] and [2]
• Merge [1, 3] and [2]: No reverse pairs as 1 < 2, 3 < 2 (no), so count is 0
• Merge [1, 3, 2] and [3, 1]: Now, check for reverse pairs where nums[i] > 2 * nums[j].
• For i=0 (1): 1 > 2 * 3? No, 1 > 2 * 1? No
• For i=1 (3): 3 > 2 * 3? No, 3 > 2 * 1? Yes (3 > 2)
• For i=2 (2): 2 > 2 * 3? No, 2 > 2 * 1? No
• So, total reverse pairs: 2 (from [3,1] and [3,1])

The merge sort approach counts these efficiently without redundant checks.

Time and Space Complexity

• Brute-Force Approach:
  • Time Complexity: O(n²) because it checks every pair (i, j).
  • Space Complexity: O(1), no extra space needed.
• Optimized Merge Sort Approach:
  • Time Complexity: O(n log n) because merge sort divides the array log n times and processes n elements at each level.
  • Space Complexity: O(n) due to the temporary arrays used during merging.

The optimized approach is essential for handling large arrays efficiently.

Summary

To solve the Reverse Pairs problem efficiently, we use a modified merge sort algorithm. This approach leverages the sorted nature of subarrays during merging to count reverse pairs in O(n log n) time, a significant improvement over the brute-force O(n²) method. The key insight is to recognize the similarity to the inversion count problem and adapt the merge step to count pairs meeting the specific condition nums[i] > 2 * nums[j]. This solution is both elegant and efficient, making it suitable for large input sizes.