Back to problems
Leetcode
Medium
Arrays
Sorting
Divide and Conquer
Binary Search
Google
Reverse Pairs
Count the number of reverse pairs in an integer array.
Acceptance 60%
Problem Statement
Problem
Given an integer array nums, count the number of reverse pairs.
A pair of indices (i, j) is a reverse pair if:
0 <= i < j < nums.length, andnums[i] > 2 * nums[j]
Return the total number of such pairs.
Notes
- The answer may be larger than what fits in a 32-bit signed integer.
- A brute-force check of all pairs is typically too slow for large arrays, so look for a more efficient approach.
Input Format
- An integer array
nums. - Each element represents an integer value in the array.
Output Format
- Return a single integer: the number of reverse pairs
(i, j)such thati < jandnums[i] > 2 * nums[j].
Constraints
1 <= nums.length- Values in
numsmay be negative, zero, or positive. - The result can exceed 32-bit integer range; use a 64-bit count.
- A solution better than is expected for interview-quality performance.
Examples
Sample cases returned by the problem API.
Example 1
Input
nums = [1,3,2,3,1]
Output
2
Explanation
The reverse pairs are (3, 1) at indices (1, 4) and (3, 1) at indices (3, 4).
Example 2
Input
nums = [2,4,3,5,1]
Output
3
Explanation
The reverse pairs are (4,1), (3,1), and (5,1).
Show 1 more example
Example 3
Input
nums = [5,4,3,2,1]
Output
4
Explanation
Valid pairs include (5,2), (5,1), (4,1), and (3,1).
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.
Guided hints
Editorial and discussion links
Concept map and variants
Track your progress
Sign in to bookmark this problem, save notes, and manage its revision plan.