How hard is LeetCode 493. Reverse Pairs?

LeetCode 493. Reverse Pairs is rated Hard on LeetCode.

Reverse Pairs — LeetCode 493 Python Solution

HardBinary Indexed TreeSegment TreeArrayBinary SearchDivide and ConquerOrdered SetMerge Sort

Problem: #493
Pattern: Monotonic Stack
Reading time: 5 min
Source: leetcode.com

The problem

Given an integer array nums, return the number of reverse pairs in the array. A reverse pair is a pair (i, j) where: 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

Example

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:

Python solution

Python

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def merge_sort(l, r):
            if l >= r:
                return 0
            mid = (l + r) >> 1
            ans = merge_sort(l, mid) + merge_sort(mid + 1, r)
            t = []
            i, j = l, mid + 1
            while i <= mid and j <= r:
                if nums[i] <= 2 * nums[j]:
                    i += 1
                else:
                    ans += mid - i + 1
                    j += 1
            i, j = l, mid + 1
            while i <= mid and j <= r:
                if nums[i] <= nums[j]:
                    t.append(nums[i])
                    i += 1
                else:
                    t.append(nums[j])
                    j += 1
            t.extend(nums[i : mid + 1])
            t.extend(nums[j : r + 1])
            nums[l : r + 1] = t
            return ans

        return merge_sort(0, len(nums) - 1)

Complexity

Measure	Complexity
Time	O(log n) or O(n log n)
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 493. Reverse Pairs is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 493. Reverse Pairs?: LeetCode 493. Reverse Pairs is rated Hard on LeetCode.
What topics does LeetCode 493. Reverse Pairs cover?: LeetCode 493. Reverse Pairs is tagged Binary Indexed Tree, Segment Tree, Array, Binary Search, Divide and Conquer, Ordered Set and Merge Sort on LeetCode.