Reverse Pairs — Merge Sort / BIT

Problem

Count important reverse pairs: i < j and nums[i] > 2 * nums[j].

Approach — Modified Merge Sort

During merge of left and right halves:

Use two pointers: for each right element, find how many left elements satisfy left[i] > 2 * right[j]
These pointers only move forward → O(n) per merge level

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

Solutions

Python

class Solution:
    def reversePairs(self, nums: list[int]) -> int:
        self.count=0
        def merge_sort(arr):
            if len(arr)<=1: return arr
            mid=len(arr)//2
            left=merge_sort(arr[:mid])
            right=merge_sort(arr[mid:])
            j=0
            for x in left:
                while j<len(right) and x>2*right[j]: j+=1
                self.count+=j
            return sorted(left+right)
        merge_sort(nums); return self.count

Complexity

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