Course4all

Reverse Pairs

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Bit Manipulation.

Reverse Pairs

Given an integer array nums, return the number of reverse pairs in the array. A reverse pair is a pair (i,j)(i, j) such that 0≤i<j<nums.length0 \leq i < j < nums.length and nums[i]>2⋅nums[j]nums[i] > 2 \cdot nums[j].
Hard

Examples

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

Level I: Brute Force (Nested Loops)

Intuition

Check every possible pair (i,j)(i, j) where i<ji < j. If the condition nums[i]>2⋅nums[j]nums[i] > 2 \cdot nums[j] is met, increment the counter.

Thought Process

  1. Use a nested loop i∈[0,n−1],j∈[i+1,n−1]i \in [0, n-1], j \in [i+1, n-1].
  2. Check if nums[i]>2⋅nums[j]nums[i] > 2 \cdot nums[j].
  3. Return count.

Pattern: All-Pairs Comparison

⏱ O(N^2) - Quadratic complexity.💾 O(1) - No extra space.
java
public class Solution {
    public int reversePairs(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((long)nums[i] > 2L * nums[j]) count++;
            }
        }
        return count;
    }
}
Approach 2

Level II: Merge Sort based Counting

Intuition

Similar to counting inversions, we can use merge sort to count reverse pairs. During the merge step, for each element in the left half, we find how many elements in the right half satisfy nums[i]>2⋅nums[j]nums[i] > 2 \cdot nums[j].
⏱ $O(N \log N)$💾 $O(N)$
java
class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }
    private int mergeSort(int[] nums, int l, int r) {
        if (l >= r) return 0;
        int m = l + (r - l) / 2;
        int res = mergeSort(nums, l, m) + mergeSort(nums, m + 1, r);
        int j = m + 1;
        for (int i = l; i <= m; i++) {
            while (j <= r && (long)nums[i] > 2L * nums[j]) j++;
            res += (j - (m + 1));
        }
        Arrays.sort(nums, l, r + 1);
        return res;
    }
}
Approach 3

Level III: Optimal (Binary Indexed Tree / Fenwick Tree)

Intuition

As we iterate through the array, we want to count how many numbers seen so far are greater than 2⋅current2 \cdot current. A Binary Indexed Tree (BIT) can efficiently handle point updates and prefix sums. Since values can be large, we use coordinate compression on all nums[i]nums[i] and 2⋅nums[i]2 \cdot nums[i].

Thought Process

  1. Collect all nums[i]nums[i] and 2⋅nums[i]2 \cdot nums[i] and sort them to create distinct ranks (Coordinate Compression).
  2. Iterate through nums from right to left (or left to right with adjustments):
    • Query BIT for how many elements are strictly less than nums[i]/2nums[i] / 2.
    • Update BIT with nums[i]nums[i].
  3. This leverages the bitwise structure of indices in the BIT.

Pattern: BIT with Coordinate Compression

⏱ O(N \log N) - Sorting takes $O(N \log N)$, and $N$ BIT operations take $O(N \log N)$.💾 O(N) - To store the BIT and rank map.
java
import java.util.*;

class Solution {
    public int reversePairs(int[] nums) {
        Set<Long> set = new TreeSet<>();
        for (int x : nums) {
            set.add((long)x);
            set.add(2L * x);
        }
        Map<Long, Integer> rank = new HashMap<>();
        int r = 1;
        for (long x : set) rank.put(x, r++);
        
        int[] bit = new int[r];
        int count = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            count += query(bit, rank.get((long)nums[i]) - 1);
            update(bit, rank.get(2L * nums[i]), 1);
        }
        return count;
    }
    
    private void update(int[] bit, int idx, int val) {
        for (; idx < bit.length; idx += idx & -idx) bit[idx] += val;
    }
    
    private int query(int[] bit, int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSum of All Subset XOR Totals
Next Question →Can I Win