Reverse Pairs | Hard DSA Interview Question

The Reverse Pairs problem is a classic hard-level Array and Divide-and-Conquer problem. Given an array of integers nums, the objective is to count the total number of reverse pairs $(i, j)$ such that $i < j$ and $\text{nums}[i] > 2 \times \text{nums}[j]$. While closely related to the traditional Count Inversions problem ($\text{nums}[i] > \text{nums}[j]$), the scalar factor of $2$ breaks the ability to count pairs directly during the merge step, requiring a decoupled two-pointer counting step integrated into Merge Sort.

1. Problem Statement & Mathematical Definition

Given an integer array nums of size $N$, find the total number of reverse pairs.

A Reverse Pair is defined as a pair of indices $(i, j)$ that satisfies two conditions simultaneously:

1. $i < j$ (the left index strictly precedes the right index).
2. $\text{nums}[i] > 2 \times \text{nums}[j]$ (the left element is strictly greater than twice the right element).

Note: Pay careful attention to strict inequality: $\text{nums}[i] > 2 \times \text{nums}[j]$. If $\text{nums}[i] = 12$ and $\text{nums}[j] = 6$, $12 > 2 \times 6$ evaluates to $12 > 12$ (False), so $(12, 6)$ is not a reverse pair.

2. Naive Brute Force Approach ($O(N^2)$)

Approach & Intuition

The most straightforward approach is to test every possible index pair $(i, j)$ using two nested loops.

• The outer loop picks the left index i from 0 to N - 1.
• The inner loop picks the right index j from i + 1 to N - 1.
• If $\text{nums}[i] > 2 \times \text{nums}[j]$, increment a counter.

Naive Code Implementation

public class Solution {
    public int reversePairsNaive(int[] nums) {
        int count = 0;
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Cast to long to avoid integer overflow when multiplying by 2
                if ((long) nums[i] > 2L * nums[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

Complexity Analysis

• Time Complexity: $O(N^2)$ — For an array of size $N$, the outer and inner loops iterate through $\frac{N(N - 1)}{2}$ pairs.
• Space Complexity: $O(1)$ — Uses only a few primitive counter variables.

3. Why Standard "Count Inversions" Logic Fails

In the standard Count Inversions problem ($\text{nums}[i] > \text{nums}[j]$), we combine counting directly into the Merge step of Merge Sort:

• If left[i] > right[j], then because left is sorted, all remaining elements from left[i] to left[mid] are also strictly greater than right[j].
• Hence, we can instantaneously add $(\text{mid} - i + 1)$ to our total count and advance j.

Why this breaks for $2 \times \text{nums}[j]$:

Consider two sorted subarrays:

• Left = [6, 13, 21, 25]
• Right = [1, 2, 3, 4, 5, 9, 11, 13]

1. Take left[0] = 6 and right[2] = 3.
2. Test condition: Is $6 > 2 \times 3$? No ($6 > 6$ is false).
3. If we used standard inversion logic, failing at $6$ might suggest $3$ cannot form pairs. However, for subsequent elements in Left ($13, 21, 25$), $3$ does form valid reverse pairs ($13 > 2 \times 3$, $21 > 2 \times 3$, $25 > 2 \times 3$).
4. Conversely, if $6$ formed a pair with $2$ ($6 > 2 \times 2$), we cannot immediately assume $6$ forms pairs with all remaining elements on the right.

The Key Structural Insight

Because multiplying by $2$ distorts the simple relative order comparison during a standard merge, we must separate the Counting step from the Merging step.

Before merging two sorted halves, we run a dedicated $O(N)$ two-pointer pass to count all valid reverse pairs between the left and right halves.

4. The Two-Pointer Counting Mechanism on Sorted Subarrays

Given two sorted halves:

• Left subarray spanned by indices [low ... mid]
• Right subarray spanned by indices [mid + 1 ... high]

We want to find how many pairs $(i, j)$ satisfy $\text{nums}[i] > 2 \times \text{nums}[j]$, where $i \in [\text{low}, \text{mid}]$ and $j \in [\text{mid} + 1, \text{high}]$.

Left (Sorted):  [6, 13, 21, 25]      (Indices low..mid)
Right (Sorted): [1, 2, 3, 4, 5, 9]   (Indices mid+1..high)

The Monotonicity Property

Since both Left and Right are sorted in ascending order:

• As i moves to the right, $\text{nums}[i]$ increases.
• If a right element $\text{nums}[\text{right}]$ satisfies $\text{nums}[i] > 2 \times \text{nums}[\text{right}]$, then for any subsequent larger left element $\text{nums}[i+1]$, the condition $\text{nums}[i+1] > 2 \times \text{nums}[\text{right}]$ will automatically hold.
• Crucial Optimization: Pointer right does NOT need to reset to mid + 1 for every new i. It only moves forward!

Step-by-Step Pointer Walkthrough

Left:  [ 6, 13, 21, 25 ]
         ^ (i)

Right: [ 1,  2,  3,  4,  5,  9 ]
         ^ (right)

1. i = 0 (nums[i] = 6):

   • Check right = 0 (nums[right] = 1): $6 > 2 \times 1 \implies 6 > 2$ (True) $\to$ Advance right.
   • Check right = 1 (nums[right] = 2): $6 > 2 \times 2 \implies 6 > 4$ (True) $\to$ Advance right.
   • Check right = 2 (nums[right] = 3): $6 > 2 \times 3 \implies 6 > 6$ (False) $\to$ Stop right.
   • Valid elements in Right for $6$: [1, 2] (Count = $2 - 0 = 2$).

2. i = 1 (nums[i] = 13):

   • right stays at index 2 (nums[right] = 3).
   • Check 3: $13 > 2 \times 3 \implies 13 > 6$ (True) $\to$ Advance right.
   • Check 4: $13 > 2 \times 4 \implies 13 > 8$ (True) $\to$ Advance right.
   • Check 5: $13 > 2 \times 5 \implies 13 > 10$ (True) $\to$ Advance right.
   • Check 9: $13 > 2 \times 9 \implies 13 > 18$ (False) $\to$ Stop right.
   • Valid elements in Right added for $13$: [3, 4, 5] (Total right advanced to index 5, count contributed = $5 - 0 = 5$).

3. i = 2 (nums[i] = 21):

   • right starts at index 5 (nums[right] = 9).
   • Check 9: $21 > 2 \times 9 \implies 21 > 18$ (True) $\to$ Advance right (to index 6, out of bounds).
   • Valid elements in Right added: [9] (Total count contributed = $6$).

4. i = 3 (nums[i] = 25):

   • right is already out of bounds (right = 6). Loop does not run.
   • Valid elements added: $6$.

5. Complete Algorithm & Merge Sort Walkthrough

Vertical Divide-and-Conquer Flow

Execution Steps at Each Sub-Level:

1. Base Case: Subarrays of length $1$ contain $0$ reverse pairs.
2. Recursive Step:
   • Divide array into Left (low to mid) and Right (mid + 1 to high).
   • Recursively call mergeSort on Left (returns count of pairs internal to Left).
   • Recursively call mergeSort on Right (returns count of pairs internal to Right).
3. Cross-Pair Counting (countPairs):
   • Count pairs $(i, j)$ where $i \in \text{Left}$ and $j \in \text{Right}$.
4. Merge Step (merge):
   • Standard Merge Sort combine step to sort elements across [low ... high].

6. Clean Production Code Implementation

Java Implementation

public class Solution {

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return mergeSort(nums, 0, nums.length - 1);
    }

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

        int mid = low + (high - low) / 2;
        int count = 0;

        // 1. Divide & solve left and right halves
        count += mergeSort(nums, low, mid);
        count += mergeSort(nums, mid + 1, high);

        // 2. Count reverse pairs across the two sorted halves
        count += countPairs(nums, low, mid, high);

        // 3. Merge the two sorted halves together
        merge(nums, low, mid, high);

        return count;
    }

    private int countPairs(int[] nums, int low, int mid, int high) {
        int count = 0;
        int right = mid + 1;

        for (int i = low; i <= mid; i++) {
            // Move 'right' pointer while condition holds
            // Cast to long to handle potential integer overflow during multiplication
            while (right <= high && (long) nums[i] > 2L * nums[right]) {
                right++;
            }
            // Number of valid elements in right half for current nums[i]
            count += (right - (mid + 1));
        }

        return count;
    }

    private void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int left = low;
        int right = mid + 1;
        int k = 0;

        while (left <= mid && right <= high) {
            if (nums[left] <= nums[right]) {
                temp[k++] = nums[left++];
            } else {
                temp[k++] = nums[right++];
            }
        }

        while (left <= mid) {
            temp[k++] = nums[left++];
        }

        while (right <= high) {
            temp[k++] = nums[right++];
        }

        for (int i = 0; i < temp.length; i++) {
            nums[low + i] = temp[i];
        }
    }
}

C++ Implementation

#include <vector>

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

private:
    int mergeSort(std::vector<int>& nums, int low, int high) {
        if (low >= high) return 0;

        int mid = low + (high - low) / 2;
        int count = 0;

        count += mergeSort(nums, low, mid);
        count += mergeSort(nums, mid + 1, high);
        count += countPairs(nums, low, mid, high);
        merge(nums, low, mid, high);

        return count;
    }

    int countPairs(std::vector<int>& nums, int low, int mid, int high) {
        int count = 0;
        int right = mid + 1;

        for (int i = low; i <= mid; i++) {
            while (right <= high && (long long)nums[i] > 2LL * nums[right]) {
                right++;
            }
            count += (right - (mid + 1));
        }
        return count;
    }

    void merge(std::vector<int>& nums, int low, int mid, int high) {
        std::vector<int> temp;
        int left = low, right = mid + 1;

        while (left <= mid && right <= high) {
            if (nums[left] <= nums[right]) {
                temp.push_back(nums[left++]);
            } else {
                temp.push_back(nums[right++]);
            }
        }

        while (left <= mid) temp.push_back(nums[left++]);
        while (right <= high) temp.push_back(nums[right++]);

        for (int i = 0; i < temp.size(); i++) {
            nums[low + i] = temp[i];
        }
    }
};

7. Complexity & Optimization Analysis

Time Complexity Analysis

1. Tree Depth: Merge sort divides the array in half at each step, producing a tree of height $O(\log N)$.
2. Work Per Level:
   • Counting Step (countPairs): Pointer i moves at most $N/2$ times. Pointer right moves at most $N/2$ times across the right subarray. Total linear work per merge level = $O(N)$.
   • Merging Step (merge): Standard two-pointer merge takes $O(N)$ operations.
3. Total Time: $T(N) = 2T(N/2) + O(N) \implies \mathbf{O(N \log N)}$.

Common Misconception: "Nested loops in countPairs make it $O(N^2)$."
Correction: The inner while loop condition advances the right pointer continuously without resetting for subsequent iterations of i. Across the entire function execution, right increments at most $(high - mid)$ times. Thus, countPairs is strictly $O(N)$.

Space Complexity Analysis

• Auxiliary Array Space: $O(N)$ auxiliary space for the temp array during the merge operations.
• Recursion Call Stack: $O(\log N)$ stack space for merge sort recursion depth.
• Total Space Complexity: $\mathbf{O(N)}$.

Interview Communication Strategy: Mention to the interviewer that this optimal approach mutates (distorts) the original array order by sorting it. If preserving the original array order is required, inform them that you would work on a deep copy of the input array.

8. Comparative Matrix

Summary and Key Takeaways

• Core Problem Distinction: Reverse Pairs requires finding elements where $\text{nums}[i] > 2 \times \text{nums}[j]$. The extra factor of $2$ invalidates the single-pass counting trick embedded inside standard Merge Sort.
• Decoupled Strategy: To preserve efficiency, decouple counting from merging. Perform counting on two sorted halves right before executing the standard merge procedure.
• Monotonic Pointer Advancement: Because both sub-arrays are sorted, as the left pointer i increases, nums[i] grows strictly larger. Consequently, the right pointer right never needs to reset, guaranteeing an $O(N)$ run-time per recursion level.
• Integer Overflow Protection: Always cast nums[j] to a 64-bit integer (long in Java, long long in C++) before multiplying by $2$ to avoid sign overflow errors with extreme integer values (e.g., INT_MAX).
• Array Mutation Flag: Be ready to clarify to an interviewer that Merge Sort sorts the array in-place, and offer an explicit array duplication if preserving the input sequence is required.