03 Nov 2023•Python•Hard

Reverse Pairs

count pairs where nums[i] > 2 * nums[j] and i < j using merge sort with counting during merge phase.

use merge sort but count reverse pairs during merge. for each element in left half, count how many elements in right half satisfy nums[i] > 2 * nums[j]. use two-pointer technique: as left element increases, right pointer can only move forward.

during merge phase, before merging, count pairs: for each left[i], find how many right[j] satisfy left[i] > 2 * right[j]. then merge normally. recursive calls handle subarrays.

counting logic

for each left[i], find j where left[i] > 2 * right[j]
count = j - (mid + 1) gives number of valid pairs
j pointer only moves forward (monotonic)
then merge arrays normally

complexity

O(n log n) time from merge sort, counting adds O(n) per level. O(n) space for temporary arrays.

Solution files

Python•reverse-pairs/solution.py

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge_sort(nums, left, right):
            if left >= right:
                return class="syntax-number">0
            
            mid = (left + right) class=class="syntax-string">"syntax-comment">// class="syntax-number">2
            count = merge_sort(nums, left, mid) + merge_sort(nums, mid + class="syntax-number">1, right)
            
            j = mid + class="syntax-number">1
            for i in range(left, mid + class="syntax-number">1):
                while j <= right and nums[i] > class="syntax-number">2 * nums[j]:
                    j += class="syntax-number">1
                count += j - (mid + class="syntax-number">1)
            
            nums[left:right + class="syntax-number">1] = sorted(nums[left:right + class="syntax-number">1])
            return count
        
        return merge_sort(nums, class="syntax-number">0, len(nums) - class="syntax-number">1)