Log inSign up
hardLeetCodeNot Started

Reverse Pairs

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) such that: - 0 <= i < j < nums.length and - nums[i] > 2 * nums[j]

Notice that the multiplication 2 * nums[j] can exceed the 32-bit signed integer range, so 64-bit integer arithmetic must be used.

Example 1 · Example 1:

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

Example 2 · Example 2:

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

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Reverse Pairs.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Reverse Pairs
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Feasible only when n <= 2000.
  • BETTER: When using Fenwick tree templates for inversion-type problems.
  • OPTIMAL: The universally demanded optimal solution for technical interviews.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Nested Loops

Intuition

Use two nested loops to check all pairs (i, j) with 0 <= i < j < n. For each pair, check if (long long)nums[i] > 2LL \cdot nums[j]. Because there are \frac{n(n - 1)}{2} pairs, this runs in O(n2) time, which times out for n = 50,000.

When to apply: Feasible only when n <= 2000.

Algorithm

  1. Step 1: Initialize count = 0.
  2. Step 2: Loop i from 0 to n - 1.
  3. Step 3: Loop j from i + 1 to n - 1.
  4. Step 4: If (long)nums[i] > 2L * nums[j], increment count.
  5. Step 5: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4int reversePairsBrute(const std::vector<int>& nums) {
5 int n = nums.size();
6 int count = 0;
7 for (int i = 0; i < n; ++i) {
8 for (int j = i + 1; j < n; ++j) {
9 if ((long long)nums[i] > 2LL * nums[j]) {
10 count++;
11 }
12 }
13 }
14 return count;
15}
16
17int main() {
18 std::vector<int> nums = {1, 3, 2, 3, 1};
19 std::cout << reversePairsBrute(nums) << std::endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(n^2) where n is nums length
  • Space complexity: O(1) auxiliary space

2. Binary Indexed Tree + Coordinate Compression

Intuition

Transform into an online frequency problem: 1. For every element x \in \text{nums}, collect both x and 2LL \cdot x into a set. 2. Coordinate compress all unique values to assign each value a rank in [1 \dots M]. 3. Initialize a Fenwick tree of size M. 4. Traverse elements from left to right: - For nums[j], query the Fenwick tree for the number of elements with rank strictly greater than \text{rank}(2LL \cdot nums[j]). - Add this count to the answer. - Insert +1 at \text{rank}(nums[j]) in the Fenwick tree. 5. Total time is O(n log n), space is O(n).

When to apply: When using Fenwick tree templates for inversion-type problems.

Algorithm

  1. Step 1: Collect all nums[i] and 2LL * nums[i] into an array, sort and deduplicate.
  2. Step 2: Allocate BIT of size equal to unique values count.
  3. Step 3: Loop j from 0 to n - 1.
  4. Step 4: Query BIT for elements strictly greater than 2LL * nums[j] and add to answer.
  5. Step 5: Add 1 to rank(nums[j]) in BIT.
  6. Step 6: Return answer count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct BIT {
6 int n;
7 std::vector<int> tree;
8 BIT(int n) : n(n), tree(n + 1, 0) {}
9 void add(int i, int delta) {
10 for (; i <= n; i += i & -i) tree[i] += delta;
11 }
12 int query(int i) {
13 int sum = 0;
14 for (; i > 0; i -= i & -i) sum += tree[i];
15 return sum;
16 }
17};
18
19int reversePairsBIT(const std::vector<int>& nums) {
20 int n = nums.size();
21 std::vector<long long> allVals;
22 for (int x : nums) {
23 allVals.push_back((long long)x);
24 allVals.push_back(2LL * x);
25 }
26 std::sort(allVals.begin(), allVals.end());
27 allVals.erase(std::unique(allVals.begin(), allVals.end()), allVals.end());
28
29 auto getRank = [&](long long v) {
30 return std::lower_bound(allVals.begin(), allVals.end(), v) - allVals.begin() + 1;
31 };
32
33 BIT bit(allVals.size());
34 int total = 0;
35
36 for (int j = 0; j < n; ++j) {
37 int rank2x = getRank(2LL * nums[j]);
38 int greater = j - bit.query(rank2x);
39 total += greater;
40 bit.add(getRank(nums[j]), 1);
41 }
42
43 return total;
44}
45
46int main() {
47 std::vector<int> nums = {1, 3, 2, 3, 1};
48 std::cout << reversePairsBIT(nums) << std::endl;
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(n log n) time
  • Space complexity: O(n) auxiliary space for ranks and Fenwick tree

3. Modified Merge Sort (Divide and Conquer)

Intuition

Divide-and-conquer using Merge Sort is the most efficient and elegant approach: 1. Divide nums into left [left, mid] and right [mid + 1, right] halves. 2. Recursively sort and count pairs in both halves. 3. Counting Cross-Pairs: - Both subarrays [left, mid] and [mid + 1, right] are sorted in ascending order. - For each index i in [left, mid]: - Advance pointer j in [mid + 1, right] while j <= right and (long long)nums[i] > 2LL \cdot nums[j]. - The number of valid right elements for this i is exactly j - (mid + 1). - Because the left subarray is sorted, when i increases, nums[i] increases, so j never needs to move backwards! - Counting takes O(right - left + 1) linear time! 4. Standard Merge: - Merge the two sorted halves into a temporary buffer in O(right - left + 1) time. 5. Total runtime is strictly O(n log n) with minimal memory footprint and no tree overhead.

When to apply: The universally demanded optimal solution for technical interviews.

Algorithm

  1. Step 1: Allocate temp array of length n for merge buffer.
  2. Step 2: Define mergeSort(left, right): if left >= right return 0.
  3. Step 3: mid = (left + right) / 2; count = mergeSort(left, mid) + mergeSort(mid + 1, right).
  4. Step 4: Maintain j = mid + 1. For each i in [left, mid], advance j while j <= right and nums[i] > 2LL * nums[j]. Add j - (mid + 1) to count.
  5. Step 5: Merge sorted halves [left, mid] and [mid + 1, right] into temp, copy back to nums.
  6. Step 6: Return count.

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Divide nums = [1, 3, 2, 3, 1] into left [1, 3, 2] and right [3, 1]
Visual state
Values and pointers at this exact step
pointers
S
1
3
2
3
1
0
↑ left
1
2
↑ mid
3
4
↑ right
Check / comparison
Split at mid index 2
Decision / next transition
Recursively sort left and right halves
Why this step matters

Divide nums = [1, 3, 2, 3, 1] into left [1, 3, 2] and right [3, 1].

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4int mergeSortCount(std::vector<int>& nums, int left, int right, std::vector<int>& temp) {
5 if (left >= right) return 0;
6 int mid = left + (right - left) / 2;
7 int count = mergeSortCount(nums, left, mid, temp) + mergeSortCount(nums, mid + 1, right, temp);
8
9 // Count reverse pairs
10 int j = mid + 1;
11 for (int i = left; i <= mid; ++i) {
12 while (j <= right && (long long)nums[i] > 2LL * nums[j]) {
13 j++;
14 }
15 count += (j - (mid + 1));
16 }
17
18 // Merge
19 int i = left, r = mid + 1, k = left;
20 while (i <= mid && r <= right) {
21 if (nums[i] <= nums[r]) temp[k++] = nums[i++];
22 else temp[k++] = nums[r++];
23 }
24 while (i <= mid) temp[k++] = nums[i++];
25 while (r <= right) temp[k++] = nums[r++];
26 for (int idx = left; idx <= right; ++idx) nums[idx] = temp[idx];
27
28 return count;
29}
30
31int reversePairs(std::vector<int>& nums) {
32 std::vector<int> temp(nums.size());
33 return mergeSortCount(nums, 0, (int)nums.size() - 1, temp);
34}
35
36int main() {
37 std::vector<int> nums = {1, 3, 2, 3, 1};
38 std::cout << reversePairs(nums) << std::endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(n log n) time
  • Space complexity: O(n) auxiliary space for temp merge array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Nested LoopsO(n^2) where n is nums lengthO(1) auxiliary spaceEvaluate every pair (i, j) with i < j and test if nums[i] > 2 * nums[j].O(n2) where n is nums length
2.Binary Indexed Tree + Coordinate CompressionO(n log n) timeO(n) auxiliary space for ranks and Fenwick treeDiscretize values nums[k] and 2 * nums[k] into ranks. Query elements strictly greater than 2 * nums[j] from a Fenwick tree.O(n log n) time
3.Modified Merge Sort (Divide and Conquer)OptimalO(n log n) timeO(n) auxiliary space for temp merge arraySort subarrays using Merge Sort. Before merging, use two pointers to count pairs where nums[i] > 2 * nums[j] in O(n log n).O(n log n) time

Common Pitfalls & Crucial Edge Cases

32-bit integer overflow

Writing nums[i] > 2 * nums[j] without 64-bit casting triggers overflow bugs for values near INT_MAX / INT_MIN.

Resetting the inner pointer during the count pass

Because both left and right halves are sorted, as i advances, the valid j only advances forward. Resetting j makes it O(N2).

O(N^2) brute force

Checking all pairs takes O(N2) and triggers TLE for N = 50,000.

Crucial Edge Cases to Validate:

  • Integer overflow on 2 * nums[j] — If nums[j] = 10^9 or -10^9, 2 * nums[j] can overflow 32-bit signed integers. Must cast to long long (nums[i] > 2LL * nums[j]).
  • Array is strictly descending `[5, 4, 3, 2, 1]` — Produces multiple reverse pairs.
  • Array is strictly ascending `[1, 2, 3, 4, 5]` — Returns 0.
  • Negative numbers `[-5, -2]` — -2 * 2 = -4, and -5 > -4 is false; negative values must follow standard 64-bit comparison.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Emphasize why counting and merging must be decoupled: explain the ratio asymmetry (nums[i] > 2 * nums[j]).
  2. Highlight 64-bit casting (2LL * nums[j]) as a critical reliability safeguard.
  3. Contrast with the Fenwick Tree + coordinate compression alternative and explain why Merge Sort is preferred here (no coordinate compression needed).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the condition for an index pair (i, j) to be a reverse pair?

2.Why cannot we count reverse pairs during the standard merge step of Merge Sort directly?

3.What is the time complexity of the modified Merge Sort algorithm for Reverse Pairs?

Back to DSA Sheet