Reverse Pairs

Description

Reverse Pairs
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

Brute Force

Explanation

We check every possible pair $(i,j)$ where $i<j$ using two nested loops and increment our counter whenever $\text{nums}[i]>2\times \text{nums}[j]$ holds true.

Complexity Analysis

• Time Complexity: $\mathcal{O}(n^2)$ — Two nested loops over $n$ elements.
• Space Complexity: $\mathcal{O}(1)$ — Uses no extra memory.

class Solution {
    public int reversePairs(int[] nums) {
        int count = 0;
        int n = nums.length;
 
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Multiplying by 2.0 promotes comparison to double to avoid integer overflow
                if (nums[i] > 2.0 * nums[j]) {
                    count++;
                }
            }
        }
 
        return count;
    }
}
 

Optimized (Modified Merge Sort)

Merge Sort Overview

Merge Sort
Standard Merge Sort splits an array into two sorted halves recursively and zips them back together in linear time ($\mathcal{O}(n)$).

What We Added: countPairs()

Right before merging two sorted halves, we insert a two-pointer scan step: countPairs().

Since both halves are individually sorted:

1. As left moves forward to larger elements in the left half, valid elements in the right half only ever grow.
2. The right pointer never resets back to the start of the right half. It moves continuously forward, allowing us to count all valid cross-pairs in linear $\mathcal{O}(n)$ time per recursion step instead of $\mathcal{O}(n^2)$.

Complexity Analysis

• Time Complexity: $\mathcal{O}(n\log n)$ — Recursion tree depth is $\log n$, with $\mathcal{O}(n)$ work (counting + merging) at each level.
• Space Complexity: $\mathcal{O}(n)$ — For the auxiliary temp array during merging.

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }
 
    public int mergeSort(int[] arr, int low, int high) {
        if (low >= high) return 0;
 
        int mid = low + (high - low) / 2;
 
        // 1. DIVIDE: Sum counts from left and right halves
        int count = mergeSort(arr, low, mid) + mergeSort(arr, mid + 1, high);
 
        // 2. COUNT: Count cross reverse pairs before merging
        count += countPairs(arr, low, mid, high);
 
        // 3. COMBINE: Standard merge step
        merge(arr, low, mid, high);
 
        return count;
    }
 
    // Two-pointer scan on sorted halves
    private int countPairs(int[] arr, int low, int mid, int high) {
        int count = 0;
        int right = mid + 1;
 
        for (int left = low; left <= mid; left++) {
            while (right <= high && (long) arr[left] > 2L * arr[right]) {
                right++; //long imp for full pass
            }
            count += (right - (mid + 1));
        }
 
        return count;
    }
 
    // Standard Merge helper
    private void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int left = low, right = mid + 1, k = 0;
 
        while (left <= mid && right <= high) {
            temp[k++] = (arr[left] <= arr[right]) ? arr[left++] : arr[right++];
        }
 
        while (left <= mid) temp[k++] = arr[left++];
        while (right <= high) temp[k++] = arr[right++];
 
        for (int i = low; i <= high; i++) {
            arr[i] = temp[i - low];
        }
    }
}
 

Key Takeaway: Integer Overflow in Comparison Operations

• The Trap: In Java, binary operations (like multiplication *) execute using the primitive types of the operands before any comparative statement is evaluated.
• The Case: For constraints reach $2^{31}-1$ (Integer.MAX_VALUE). Evaluating 2 * nums[right] with standard 32-bit integer arithmetic wraps around to negative values when $nums[right]>1073741823$.
• Why (long) nums[left] > 2 * nums[right] Fails: Casting only the left side converts $nums[left]$ to long, but the right side 2 * nums[right] still evaluates as standard 32-bit int multiplication first (overflowing to negative values) before being promoted to long for comparison.
• The Solution: Cast either the constant multiplier to a long literal (2L) or cast $nums[right]$ to long to force 64-bit promotion during multiplication:

while (right <= high && (long) nums[left] > 2L * nums[right]) right++;

---

The key reason we write it this way comes down to speed and how sorted arrays behave.
If you write a straightforward condition, you would check every right from scratch for every single left:

// Naive straight-forward counting: O(n^2)
for (int left = low; left <= mid; left++) {
    for (int right = mid + 1; right <= high; right++) {
        if (arr[left] > 2.0 * arr[right]) {
            count++;
        }
    }
}
 

This brute-force double loop checks all combinations, making it slow ($\mathcal{O}(n^2)$) and defeating the whole purpose of Merge Sort.

---

The Smart Way: Why right Keeps Moving Forward

Since both halves are already sorted in ascending order:

1. right only pushes forward: If arr[left] > 2.0 * arr[right] is true for arr[right], the while loop moves right forward until it finds a number that is too big to satisfy the condition.
2. right points to the boundary: When the while loop stops, every element in the right half from index mid + 1 up to right - 1 is valid!
3. How many valid elements is that?

$\text{Count of valid elements}=\text{Current Index }(\text{right})-\text{Start Index }(\text{mid}+1)$

Walkthrough Example

Suppose our sorted halves are:

• Left half: [6, 10] (low = 0, mid = 1)
• Right half: [1, 2, 4] (mid + 1 = 2, high = 4)

Step 1: left = 0 (arr[left] = 6)

• Start right = 2 (arr[right] = 1).
• 6 > 2.0 * 1 $\to$ Valid! Move right to 3 (arr[right] = 2).
• 6 > 2.0 * 2 $\to$ Valid! Move right to 4 (arr[right] = 4).
• 6 > 2.0 * 4 $\to$ False (6 is not > 8). Loop stops at right = 4.
• Count calculation: right - (mid + 1) = 4 - 2 = 2.
  (Elements 1 and 2 were valid).

Step 2: left = 1 (arr[left] = 10)

• Because 10 is larger than 6, we do not reset right back to 2! Elements 1 and 2 are guaranteed to satisfy 10 > 2 * arr[right].
• We resume checking from right = 4 (arr[right] = 4):
• 10 > 2.0 * 4 $\to$ Valid! Move right to 5 (high + 1). Loop stops.
• Count calculation: right - (mid + 1) = 5 - 2 = 3.
  (Elements 1, 2, and 4 are valid).

Because right never resets back to mid + 1, the inner while loop runs at most $N$ times across the entire outer loop, giving us an optimal $\mathcal{O}(n)$ time complexity.