reverse-pairs

< Previous 　　　　　　　　　　　　　　　　 Next >

493. Reverse Pairs (Hard)

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 1:

Input: nums = [1,3,2,3,1]
Output: 2

Example 2:

Input: nums = [2,4,3,5,1]
Output: 3

 

Constraints:

• 1 <= nums.length <= 5 * 104
• -231 <= nums[i] <= 231 - 1

Related Topics

[Binary Indexed Tree] [Segment Tree] [Array] [Binary Search] [Divide and Conquer] [Ordered Set] [Merge Sort]

Similar Questions

1. Count of Smaller Numbers After Self (Hard)
2. Count of Range Sum (Hard)