Reverse Pairs

Problem Id: 493 Difficulty: Hard


Intuition

Solution


class Solution:
    def merge(self, nums, lo, mid, hi):
        i = lo
        j = mid
        index = lo
        while i < mid and j < hi:
            if nums[i] < nums[j]:
                self.aux[index] = nums[i]
                i += 1
            else:
                self.aux[index] = nums[j]
                j += 1
            index += 1

        self.aux[index:hi] = nums[j:hi] if j < hi else nums[i:mid]

        nums[lo:hi] = self.aux[lo:hi]

    def mergesort(self, nums, lo, hi):
        if hi - lo <= 1:
            return
        mid = (lo + hi) // 2
        self.mergesort(nums, lo, mid)
        self.mergesort(nums, mid, hi)

        # Additional part to calculate reverse pairs
        i = lo
        j = mid
        while j < hi:
            while i < mid and nums[i] <= 2 * nums[j]:
                i += 1
            if i == mid:
                break
            self.ans += mid - i
            j += 1

        self.merge(nums, lo, mid, hi)

    def reversePairs(self, nums: List[int]) -> int:
        self.ans = 0
        self.aux = [0] * len(nums)
        self.mergesort(nums, 0, len(nums))
        return self.ans