Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Reverse Pairs

Reverse Pairs

Master this topic with zero to advance depth.

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;
    }
}
← Previous QuestionSum of All Subset XOR Totals
Next Question →Can I Win