Skip to main content
Talentd

Reverse Pairs - Solution & Explanation

HardArrayBinary SearchDivide and ConquerBinary Indexed Tree17 min readAsked at: Amazon, Microsoft, Apple +6
Practice this problem

Problem Statement

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
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Example 2:

Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

 

Constraints:

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

Approach Overview

Problem Overview: Given an integer array nums, count pairs (i, j) such that i < j and nums[i] > 2 * nums[j]. The challenge is detecting these pairs efficiently without checking every combination.

Approach 1: Naive Brute Force (O(n2) time, O(1) space)

The straightforward solution checks every pair of indices. Use two nested loops: fix i, then iterate j from i + 1 to the end of the array. For each pair, test the condition nums[i] > 2 * nums[j] and increment a counter when it holds. This approach requires no additional data structures and is easy to implement in any language. However, the nested iteration results in quadratic time, which becomes too slow when the array size grows into tens of thousands. The brute force version mainly helps validate correctness or build intuition before implementing an optimized algorithm.

Approach 2: Optimized Merge Sort (O(n log n) time, O(n) space)

The optimal solution uses a modified merge sort with a divide and conquer strategy. While splitting the array into halves and sorting them, you also count valid reverse pairs across the two halves. Because each half is already sorted, you can efficiently detect pairs using a two-pointer scan before merging. For each element in the left half, advance a pointer in the right half while nums[i] > 2 * nums[j]. The number of valid indices skipped contributes to the reverse pair count.

After counting cross-half pairs, perform the standard merge step to combine the two sorted halves. Sorting during recursion guarantees that each level can count pairs in linear time. Since merge sort has log n levels and each level processes n elements, the overall complexity becomes O(n log n). This technique is closely related to counting inversions in arrays and frequently appears in problems involving ordered relationships.

Although other advanced solutions exist using a Binary Indexed Tree, segment tree, or ordered set, the merge sort approach is typically preferred because it is easier to implement and performs reliably across languages without requiring coordinate compression or additional indexing tricks.

Recommended for interviews: The optimized merge sort solution is the expected answer in most interviews. It demonstrates your understanding of divide-and-conquer counting techniques and how sorted subarrays enable faster pair detection. Starting with the brute force explanation shows clear reasoning, but implementing the O(n log n) merge sort solution proves you can optimize beyond quadratic scans.

Approach 1: Naive Brute Force Approach

The simplest way to solve the problem is by checking each possible pair in the array and counting those that fit the reverse pair condition, nums[i] > 2 * nums[j].

This approach involves nested loops where the first loop picks a number and the second loop checks all numbers coming after it.

This solution utilizes two loops to iterate over all pairs in the array, checking if they match the reverse pair condition.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) because of the nested loops.
Space Complexity: O(1) as it uses constant extra space.

Try this approach in the editor →

Approach 2: Optimized Merge Sort Approach

To count reverse pairs more efficiently, use a modified merge sort algorithm.
The key is to sort the array while counting the reverse pairs as the elements are merged. As the merge sort combines two sorted subarrays, it's easier to count the number of elements that satisfy the reverse pair condition in a divide and conquer manner.

During the merge step, while comparing an element from the left array with one from the right array, if nums[i] > 2 * nums[j], every element after nums[j] in the right array will satisfy the condition with nums[i]. Hence, increment the counter for such conditions.

In this C implementation of the merge sort, we maintain a temporary array for merging while counting reverse pairs whenever we find an element in the left part that is greater than twice an element in the right part.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to merge sort steps.
Space Complexity: O(n) for the temporary array used in merging.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Brute Force Approach

Time Complexity: O(n^2) because of the nested loops.
Space Complexity: O(1) as it uses constant extra space.

Optimized Merge Sort Approach

Time Complexity: O(n log n) due to merge sort steps.
Space Complexity: O(n) for the temporary array used in merging.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Brute ForceO(n^2)O(1)Good for understanding the problem or very small arrays
Merge Sort (Divide and Conquer)O(n log n)O(n)Preferred solution for interviews and large inputs

Video Solution

Reverse Pairs | Hard Interview Question • take U forward • 393,485 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Reverse Pairs easy or hard?
Reverse Pairs is classified as a hard problem on LeetCode. The difficulty comes from recognizing that brute force is too slow and applying a modified merge sort or advanced data structures to count pairs efficiently.
How to solve Reverse Pairs in O(n)?
An O(n) solution is not known for the general case because the problem requires comparing elements across many index combinations. The best practical approach is O(n log n) using merge sort, Binary Indexed Tree, or segment tree techniques.
What is the best approach for Reverse Pairs?
The most widely accepted solution uses a modified merge sort. During the merge step, both halves are already sorted, which allows efficient counting of pairs where nums[i] > 2 * nums[j]. This reduces the complexity from O(n^2) to O(n log n).
What data structure is used in Reverse Pairs?
Common solutions rely on merge sort with divide-and-conquer. Alternative implementations may use Binary Indexed Trees, segment trees, or ordered sets combined with coordinate compression to track counts efficiently.
What is the time complexity of Reverse Pairs?
The optimal merge sort solution runs in O(n log n) time with O(n) auxiliary space. A brute force approach that checks every pair requires O(n^2) time and is too slow for large arrays.
Is Reverse Pairs asked at Google, Amazon, or Meta?
Reverse Pairs is a well-known hard interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of divide-and-conquer algorithms, merge sort modifications, and advanced counting techniques.
Is there a Python or Java solution for Reverse Pairs?
Yes. The merge sort approach is commonly implemented in Python, Java, C++, and other languages. The logic remains the same: recursively split the array, count cross-half reverse pairs using two pointers, then merge the sorted halves.

Ready to solve this problem?

Practice Reverse Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count of Range Sum

Next

Count of Smaller Numbers After Self