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.

Description Hints 3 Solution Video 32:26

493. Reverse Pairs

Hard35.1% acceptance9 companies

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 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

Asked at 9 companies

eBay Intuit

Google Microsoft

Deloitte Amazon Meta Bloomberg Apple

Topics

Hints open one at a time

Hint 1

Use the merge-sort technique.

Hint 2

Divide the array into two parts and sort them.

Hint 3

For each integer in the first part, count the number of integers that satisfy the condition from the second part. Use the pointer to help you in the counting process.

32:26

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution