Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Reverse Pairs

HARDProblemSolveExternal Links

Description

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]

In other words, you need to count how many ordered pairs of indices exist such that the element at the earlier index is strictly more than twice the element at the later index.

Examples

Example 1

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

Output: 2

Explanation: The reverse pairs are:

  • (1, 4): nums[1] = 3 and nums[4] = 1. Check: 3 > 2 × 1 = 2. Yes, 3 > 2. This is a reverse pair.
  • (3, 4): nums[3] = 3 and nums[4] = 1. Check: 3 > 2 × 1 = 2. Yes, 3 > 2. This is a reverse pair.

No other pair of indices satisfies nums[i] > 2 * nums[j], so the answer is 2.

Example 2

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

Output: 3

Explanation: The reverse pairs are:

  • (1, 4): nums[1] = 4, nums[4] = 1. Check: 4 > 2 × 1 = 2. Yes. Reverse pair.
  • (2, 4): nums[2] = 3, nums[4] = 1. Check: 3 > 2 × 1 = 2. Yes. Reverse pair.
  • (3, 4): nums[3] = 5, nums[4] = 1. Check: 5 > 2 × 1 = 2. Yes. Reverse pair.

All three pairs involve index 4 (value 1), which is small enough that several earlier elements exceed twice its value.

Example 3

Input: nums = [5, 2]

Output: 1

Explanation: Only one pair exists: (0, 1). Check: nums[0] = 5 > 2 × nums[1] = 2 × 2 = 4. Yes, 5 > 4. So the answer is 1.

Constraints

  • 1 ≤ nums.length ≤ 5 × 10^4
  • -2^31 ≤ nums[i] ≤ 2^31 - 1

Editorial

Brute Force

Intuition

The most natural approach is to check every possible pair of indices (i, j) where i < j and see whether nums[i] > 2 * nums[j]. We use two nested loops: the outer loop fixes the left element, and the inner loop tries every element to its right.

Think of it like a teacher checking every pair of students' scores. For each student, the teacher looks at every student who came after them and asks: "Is the first student's score more than double the second student's score?" If yes, that is a reverse pair. The teacher counts all such pairs across the entire class.

Step-by-Step Explanation

Let's trace through with nums = [1, 3, 2, 3, 1]:

Step 1: Fix i = 0 (nums[0] = 1). Check all j > 0:

  • j = 1: 1 > 2 × 3 = 6? No.
  • j = 2: 1 > 2 × 2 = 4? No.
  • j = 3: 1 > 2 × 3 = 6? No.
  • j = 4: 1 > 2 × 1 = 2? No.
  • count = 0.

Step 2: Fix i = 1 (nums[1] = 3). Check all j > 1:

  • j = 2: 3 > 2 × 2 = 4? No.
  • j = 3: 3 > 2 × 3 = 6? No.
  • j = 4: 3 > 2 × 1 = 2? Yes! count = 1.

Step 3: Fix i = 2 (nums[2] = 2). Check all j > 2:

  • j = 3: 2 > 2 × 3 = 6? No.
  • j = 4: 2 > 2 × 1 = 2? No (2 is NOT strictly greater than 2).
  • count stays 1.

Step 4: Fix i = 3 (nums[3] = 3). Check all j > 3:

  • j = 4: 3 > 2 × 1 = 2? Yes! count = 2.

Step 5: i = 4 is the last element — no j exists beyond it.

Result: count = 2.

Brute Force — Checking All Pairs for Reverse Pairs — Watch how we systematically check every pair (i, j) with i < j to see if nums[i] > 2 * nums[j]. Most pairs fail the condition; we count only those that pass.

Algorithm

  1. Initialize a counter count = 0.
  2. For each index i from 0 to n - 2:
    • For each index j from i + 1 to n - 1:
      • If nums[i] > 2 * nums[j], increment count.
  3. Return count.

Important: When computing 2 * nums[j], use long (64-bit integer) to avoid integer overflow, since nums[j] can be up to 2^31 - 1.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((long long)nums[i] > 2LL * nums[j]) {
                    count++;
                }
            }
        }
        return count;
    }
};
class Solution:
    def reversePairs(self, nums: list[int]) -> int:
        n = len(nums)
        count = 0
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] > 2 * nums[j]:
                    count += 1
        return count
class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((long) nums[i] > 2L * nums[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times, and for each value of i, the inner loop runs up to n - i - 1 times. The total number of pair checks is n × (n - 1) / 2, which is O(n²). For n = 50,000 this means roughly 1.25 billion comparisons — far too slow.

Space Complexity: O(1)

We only use a single counter variable. No additional data structures are needed.

Why This Approach Is Not Efficient

With n up to 50,000, the brute force performs about 1.25 × 10^9 pair comparisons. This will almost certainly exceed the time limit on any online judge.

The core problem is that for each element, we are doing a linear scan of all elements to its right. We are not leveraging any structure or order within the array.

The key insight comes from a technique used in counting inversions: merge sort. During the merge step of merge sort, we have two sorted halves. Because both halves are sorted, we can count how many elements in the left half satisfy nums[i] > 2 * nums[j] for each element in the right half — not one-by-one, but in bulk. If nums[i] > 2 * nums[j], then all elements from index i to the end of the left half also satisfy the condition (since the left half is sorted in ascending order). This transforms the counting from O(n²) to O(n log n).

Optimal Approach - Modified Merge Sort

Intuition

This problem is a variation of the classic "count inversions" problem, but with the condition nums[i] > 2 * nums[j] instead of simply nums[i] > nums[j].

The idea is to use merge sort as a framework. Merge sort naturally divides the array into halves and processes them recursively. At each merge step, we have two sorted subarrays. Because both subarrays are sorted, we can efficiently count cross-pairs (pairs where one element is in the left half and the other is in the right half) using a two-pointer technique.

Here is the core insight: suppose the left half is sorted as [a₁, a₂, ..., aₘ] and the right half is sorted as [b₁, b₂, ...]. For a fixed bⱼ in the right half, we want the count of elements aᵢ in the left half where aᵢ > 2 * bⱼ. Because the left half is sorted, once we find the first aᵢ that exceeds 2 * bⱼ, all subsequent elements (aᵢ₊₁, aᵢ₊₂, ..., aₘ) will also exceed it. So we can add (m - i + 1) pairs in one step instead of checking each individually.

The algorithm has two phases at each merge step:

  1. Count phase: Use two pointers to count reverse pairs across the two sorted halves.
  2. Merge phase: Standard merge of the two sorted halves to maintain the sorted order for the next recursion level.

These two phases are done separately to avoid mixing up the counting logic with the reordering logic.

Diagram showing how merge sort splits array and counts reverse pairs at each merge step
Diagram showing how merge sort splits array and counts reverse pairs at each merge step

Step-by-Step Explanation

Let's trace through with nums = [1, 3, 2, 3, 1]. We will focus on the merge steps where counting happens.

Recursion splits the array:

  • [1, 3, 2, 3, 1] → left = [1, 3, 2], right = [3, 1]
  • [1, 3, 2] → left = [1, 3], right = [2]
  • [1, 3] → left = [1], right = [3]
  • [3, 1] → left = [3], right = [1]

Step 1: Merge [1] and [3] (left half of [1, 3, 2])

  • Count phase: i=0, j=0. Is nums[i]=1 > 2*nums[j]=6? No. Move i. i exceeds mid. Count = 0.
  • Merge phase: Merge to get [1, 3].

Step 2: Merge [1, 3] and [2] (forming sorted [1, 3, 2] → [1, 2, 3])

  • Count phase: i=0, j=0. Is 1 > 22=4? No. Move i. Is 3 > 22=4? No. Move i. Count = 0.
  • Merge phase: Merge to get [1, 2, 3].

Step 3: Merge [3] and [1] (right half [3, 1])

  • Count phase: i=0, j=0. Is 3 > 2*1=2? Yes! Add (mid - i + 1) = (0 - 0 + 1) = 1. Move j. Count = 1.
  • Merge phase: Merge to get [1, 3].

Step 4: Final merge of [1, 2, 3] and [1, 3]

  • Count phase with two pointers on sorted halves:
    • i=0, j=0: Is left[0]=1 > 2*right[0]=2? No. Move i.
    • i=1, j=0: Is left[1]=2 > 2*right[0]=2? No. Move i.
    • i=2, j=0: Is left[2]=3 > 2*right[0]=2? Yes! Add (mid - i + 1) = (2 - 2 + 1) = 1. Move j.
    • i=2, j=1: Is left[2]=3 > 2*right[1]=6? No. Move i. i exceeds mid.
    • Count from this merge = 1.
  • Merge phase: Merge to get [1, 1, 2, 3, 3].

Total: 0 + 0 + 1 + 1 = 2 reverse pairs.

Modified Merge Sort — Counting Reverse Pairs — Watch the key merge step where we count reverse pairs between two sorted halves [1, 2, 3] and [1, 3] using two pointers, then merge them.

Algorithm

  1. Define a recursive function mergeSort(nums, left, right) that returns the count of reverse pairs in the subarray nums[left..right].
  2. Base case: If left >= right, return 0 (a single element has no pairs).
  3. Divide: Compute mid = (left + right) / 2. Recursively count pairs in mergeSort(nums, left, mid) and mergeSort(nums, mid+1, right). Sum the two counts.
  4. Count cross-pairs: Use two pointers i = left and j = mid + 1. While both pointers are in range:
    • If nums[i] <= 2 * nums[j], increment i (current left element is too small).
    • Else, all elements from i to mid form reverse pairs with nums[j]. Add (mid - i + 1) to the count and increment j.
  5. Merge phase: Perform standard merge of the two sorted halves into a temporary array, then copy back to nums.
  6. Return the total count.

Critical detail: Use 64-bit integers (long long in C++, long in Java) when computing 2 * nums[j] to avoid integer overflow, since nums[j] can be as large as 2^31 - 1.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }

private:
    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;

        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid)
                  + mergeSort(nums, mid + 1, right);

        // Count cross reverse pairs
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long long)nums[i] > 2LL * nums[j]) {
                j++;
            }
            count += (j - (mid + 1));
        }

        // Standard merge
        vector<int> temp;
        int p1 = left, p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            if (nums[p1] <= nums[p2]) {
                temp.push_back(nums[p1++]);
            } else {
                temp.push_back(nums[p2++]);
            }
        }
        while (p1 <= mid) temp.push_back(nums[p1++]);
        while (p2 <= right) temp.push_back(nums[p2++]);

        for (int i = left; i <= right; i++) {
            nums[i] = temp[i - left];
        }

        return count;
    }
};
class Solution:
    def reversePairs(self, nums: list[int]) -> int:
        def merge_sort(left: int, right: int) -> int:
            if left >= right:
                return 0

            mid = (left + right) // 2
            count = merge_sort(left, mid) + merge_sort(mid + 1, right)

            # Count cross reverse pairs
            j = mid + 1
            for i in range(left, mid + 1):
                while j <= right and nums[i] > 2 * nums[j]:
                    j += 1
                count += (j - (mid + 1))

            # Standard merge
            temp = []
            p1, p2 = left, mid + 1
            while p1 <= mid and p2 <= right:
                if nums[p1] <= nums[p2]:
                    temp.append(nums[p1])
                    p1 += 1
                else:
                    temp.append(nums[p2])
                    p2 += 1
            temp.extend(nums[p1:mid + 1])
            temp.extend(nums[p2:right + 1])
            nums[left:right + 1] = temp

            return count

        return merge_sort(0, len(nums) - 1)
class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;

        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid)
                  + mergeSort(nums, mid + 1, right);

        // Count cross reverse pairs
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long) nums[i] > 2L * nums[j]) {
                j++;
            }
            count += (j - (mid + 1));
        }

        // Standard merge
        int[] temp = new int[right - left + 1];
        int p1 = left, p2 = mid + 1, k = 0;
        while (p1 <= mid && p2 <= right) {
            if (nums[p1] <= nums[p2]) {
                temp[k++] = nums[p1++];
            } else {
                temp[k++] = nums[p2++];
            }
        }
        while (p1 <= mid) temp[k++] = nums[p1++];
        while (p2 <= right) temp[k++] = nums[p2++];

        for (int i = left; i <= right; i++) {
            nums[i] = temp[i - left];
        }

        return count;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Merge sort divides the array into log n levels. At each level, we process all n elements twice — once for counting reverse pairs and once for merging. Both the count phase and the merge phase use two-pointer techniques that run in O(n) at each level. Therefore the total time is O(n log n).

For n = 50,000, this is approximately 50,000 × 17 ≈ 850,000 operations — well within time limits.

Space Complexity: O(n)

We use a temporary array of up to n elements for the merge step at each recursion level. The recursion stack adds O(log n) depth. Since O(n) + O(log n) = O(n), the overall space complexity is O(n).