HardNo. 0493
Reverse Pairs — LeetCode 493 Python Solution
- Pattern
- Monotonic Stack
- Topics
- Binary Indexed Tree, Segment Tree, Array, Binary Search, Divide and Conquer, Ordered Set, Merge Sort
- 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
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
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0315 | Count of Smaller Numbers After Self | Hard |
| 0327 | Count of Range Sum | Hard |
| 1649 | Create Sorted Array through Instructions | Hard |
| 2179 | Count Good Triplets in an Array | Hard |
| 2426 | Number of Pairs Satisfying Inequality | Hard |
| 2659 | Make Array Empty | Hard |
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.