Reverse Pairs - Leetcode Solution

The Reverse Pairs problem on LeetCode requires finding the number of pairs (i, j) where i < j and nums[i] > 2 * nums[j]. The nums array is an integer array of length n. The goal is to come up with an efficient algorithm to solve this problem.

One simple approach to solving this problem is to use brute force. We can compare each pair of elements in the array and count the number of pairs that satisfy the above condition. However, this approach has a time complexity of O(n^2) and is not efficient for large arrays.

A more efficient approach to solving this problem involves using a modified version of merge sort. We can use the divide and conquer strategy to split the array into two halves and recursively solve for each half. Once we have solved for the two halves, we can merge them together while counting the number of pairs that satisfy the given condition.

The key observation in this approach is that the number of reverse pairs can only be found between elements in separate subarrays. This is because if the subarrays are sorted, any reverse pairs must involve an element in the left subarray and an element in the right subarray.

The algorithm for solving this problem using divide and conquer merge sort is as follows:

1. Define a function to count the number of reverse pairs between two sorted halves of the array. The function takes in two sorted subarrays, the left and right subarrays, as well as their respective lengths.

2. Initialize a count variable to 0.

3. Use two indices i and j to traverse the left and right subarrays, respectively.

4. For each element in the left subarray, find the number of elements in the right subarray that satisfy the given condition (nums[i] > 2 * nums[j]). This can be done using binary search since the right subarray is sorted.

5. Add the number of reverse pairs found to the count variable and advance the left index.

6. Merge the two subarrays together to form a single sorted array and return the count variable.

7. Define a recursive function to split the array into two halves and solve for each half.

8. Once the two halves are solved, merge them together while counting the number of reverse pairs as described above.

9. Return the total count of reverse pairs found.

The time complexity of this algorithm is O(n log n) since the merge sort algorithm has a time complexity of O(n log n).

Here is the code to implement the above algorithm in Python:

def reversePairs(nums: List[int]) -> int:
    def merge(left: List[int], right: List[int], m: int, n: int) -> int:
        i, j = 0, 0
        count = 0
        while i < m and j < n:
            if left[i] > 2 * right[j]:
                count += m - i
                j += 1
            else:
                i += 1
        return count

    def merge_sort(nums: List[int], n: int) -> int:
        if n <= 1:
            return 0
        mid = n // 2
        left = nums[:mid]
        right = nums[mid:]
        count = merge_sort(left, mid) + merge_sort(right, n - mid) + merge(left, right, mid, n - mid)
        nums[:] = sorted(nums)
        return count
    
    return merge_sort(nums, len(nums))

Overall, the above algorithm is very efficient and solves the Reverse Pairs problem on LeetCode with a time complexity of O(n log n).

1