Reverse Pairs

Hard

#0480Time: O(N^2), where N is the number of elements in the array. The two nested loops result in a quadratic number of pair comparisons.Space: O(1), as we only use a constant amount of extra space for the counter and loop indices.

Algorithms

Binary Search Divide and Conquer Merge Sort

Data structures

Array Binary Indexed Tree Segment Tree Ordered Set

Prompt

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 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

Approaches

2 approaches with complexity analysis and trade-offs.

This is the most straightforward approach, which involves checking every possible pair of indices (i, j) where i < j and testing if they satisfy the reverse pair condition.

Algorithm

Initialize a counter count to 0.
Use two nested loops. The outer loop iterates with index i from 0 to n-1.
The inner loop iterates with index j from i + 1 to n-1.
Inside the inner loop, check if the condition (long)nums[i] > 2 * (long)nums[j] is met. Casting to long is important to prevent integer overflow.
If the condition is true, increment the count.
After the loops complete, return the final count.

Walkthrough

The algorithm iterates through all possible pairs of elements in the array. For each element nums[i], it scans the rest of the array to its right (elements nums[j] where j > i). For each such pair, it checks if nums[i] is greater than 2 * nums[j]. A counter is used to keep track of how many such pairs are found. To avoid potential integer overflow when calculating 2 * nums[j] (since nums[j] can be large), it's crucial to cast the numbers to a 64-bit integer type (long in Java) before performing the multiplication and comparison.

1class Solution {2    public int reversePairs(int[] nums) {3        int count = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                if ((long) nums[i] > 2 * (long) nums[j]) {8                    count++;9                }10            }11        }12        return count;13    }14}

Complexity

Time

O(N^2), where N is the number of elements in the array. The two nested loops result in a quadratic number of pair comparisons.

Space

O(1), as we only use a constant amount of extra space for the counter and loop indices.

Trade-offs

Pros

Very simple to understand and implement.
Requires no extra space apart from a few variables for loops and the counter.

Cons

Highly inefficient for large arrays. It will result in a "Time Limit Exceeded" (TLE) error for the given constraints (N <= 5 * 10^4).

A much more efficient approach is to use a divide-and-conquer strategy, specifically by modifying the Merge Sort algorithm. The core idea is that while merging two sorted subarrays, we can efficiently count the reverse pairs that span across these two halves.

Algorithm

Define a recursive function mergeSortAndCount(nums, low, high).
Base Case: If low >= high, it means the subarray has 0 or 1 element, so return 0.
Divide: Find the middle index mid = low + (high - low) / 2.
Conquer: Recursively call the function for the left half (low to mid) and the right half (mid + 1 to high). Sum their results: count = mergeSortAndCount(nums, low, mid) + mergeSortAndCount(nums, mid + 1, high).
Combine & Count:
- This is the key step. Both halves nums[low...mid] and nums[mid+1...high] are now sorted.
- Count pairs (i, j) where i is in the left half and j is in the right. Use two pointers: i for the left half and j for the right.
- For each i from low to mid, advance j in the right half as long as (long)nums[i] > 2L * nums[j]. The number of such j's found is j - (mid + 1). Add this to count.
- Since both subarrays are sorted, the j pointer does not need to be reset for each i, making this counting step O(N).
Merge: Perform a standard merge operation to combine the two sorted halves into a single sorted array. This is crucial for the correctness of the parent recursive calls.
Return the total count.

Walkthrough

This algorithm recursively splits the array into two halves until we have subarrays of size 1. Then, as it merges the subarrays back, it counts the reverse pairs. The total count is the sum of reverse pairs within the left half, within the right half, and across the two halves.

The crucial part is counting the pairs (i, j) where i is in the left sorted half and j is in the right sorted half. Since both halves are sorted, we can do this in linear time. We use two pointers. For each element nums[i] in the left half, we find the number of elements nums[j] in the right half that satisfy nums[i] > 2 * nums[j]. Because the arrays are sorted, we can find these counts efficiently without re-scanning the right half for every element of the left half. After counting, the two halves are merged to maintain the sorted order for the upper levels of recursion.

1class Solution {2    public int reversePairs(int[] nums) {3        if (nums == null || nums.length == 0) {4            return 0;5        }6        return mergeSort(nums, 0, nums.length - 1);7    }8 9    private int mergeSort(int[] nums, int low, int high) {10        if (low >= high) {11            return 0;12        }13        int mid = low + (high - low) / 2;14        int count = mergeSort(nums, low, mid) + mergeSort(nums, mid + 1, high);15        16        // Count reverse pairs where one element is in the left half and the other in the right17        int j = mid + 1;18        for (int i = low; i <= mid; i++) {19            while (j <= high && (long)nums[i] > 2L * nums[j]) {20                j++;21            }22            count += j - (mid + 1);23        }24        25        // Merge the two sorted halves26        merge(nums, low, mid, high);27        28        return count;29    }30 31    private void merge(int[] nums, int low, int mid, int high) {32        int[] temp = new int[high - low + 1];33        int i = low, j = mid + 1, k = 0;34        while (i <= mid && j <= high) {35            if (nums[i] <= nums[j]) {36                temp[k++] = nums[i++];37            } else {38                temp[k++] = nums[j++];39            }40        }41        while (i <= mid) {42            temp[k++] = nums[i++];43        }44        while (j <= high) {45            temp[k++] = nums[j++];46        }47        for (int l = 0; l < temp.length; l++) {48            nums[low + l] = temp[l];49        }50    }51}

Complexity

Time

O(N log N). The algorithm's recurrence relation is T(N) = 2T(N/2) + O(N), which solves to O(N log N). The O(N) part comes from the linear-time scan for counting pairs and the linear-time merge operation at each level of recursion.

Space

O(N), due to the temporary array required for the merge step of the algorithm. The recursion depth adds O(log N) to the call stack, but the O(N) space for the merge buffer dominates.

Trade-offs

Pros

Highly efficient and optimal, passing the time limits for large inputs.
It is a classic and elegant application of the divide-and-conquer paradigm.

Cons

More complex to implement and reason about compared to the brute-force approach.
It either modifies the input array or requires an auxiliary array of the same size.

Solutions

Solution

1class Solution {2public3  int reversePairs(int[] nums) {4    TreeSet<Long> ts = new TreeSet<>();5    for (int num : nums) {6      ts.add((long)num);7      ts.add((long)num * 2);8    }9    Map<Long, Integer> m = new HashMap<>();10    int idx = 0;11    for (long num : ts) {12      m.put(num, ++idx);13    }14    BinaryIndexedTree tree = new BinaryIndexedTree(m.size());15    int ans = 0;16    for (int i = nums.length - 1; i >= 0; --i) {17      int x = m.get((long)nums[i]);18      ans += tree.query(x - 1);19      tree.update(m.get((long)nums[i] * 2), 1);20    }21    return ans;22  }23} class BinaryIndexedTree {24private25  int n;26private27  int[] c;28public29  BinaryIndexedTree(int n) {30    this.n = n;31    c = new int[n + 1];32  }33public34  void update(int x, int delta) {35    while (x <= n) {36      c[x] += delta;37      x += lowbit(x);38    }39  }40public41  int query(int x) {42    int s = 0;43    while (x > 0) {44      s += c[x];45      x -= lowbit(x);46    }47    return s;48  }49public50  static int lowbit(int x) { return x & -x; }51}

1class BinaryIndexedTree { public: int n ; vector < int > c ; BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += lowbit ( x ); } } int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= lowbit ( x ); } return s ; } int lowbit ( int x ) { return x & - x ; } }; class Solution { public: int reversePairs ( vector < int >& nums ) { set < long long > s ; for ( int num : nums ) { s . insert ( num ); s . insert ( num * 2ll ); } unordered_map < long long , int > m ; int idx = 0 ; for ( long long num : s ) m [ num ] = ++ idx ; BinaryIndexedTree * tree = new BinaryIndexedTree ( m . size ()); int ans = 0 ; for ( int i = nums . size () - 1 ; i >= 0 ; -- i ) { ans += tree -> query ( m [ nums [ i ]] - 1 ); tree -> update ( m [ nums [ i ] * 2ll ], 1 ); } return ans ; } };

1class BinaryIndexedTree : def __init__ ( self , n ): self . n = n self . c = [ 0 ] * ( n + 1 ) @ staticmethod def lowbit ( x ): return x & - x def update ( self , x , delta ): while x <= self . n : self . c [ x ] += delta x += BinaryIndexedTree . lowbit ( x ) def query ( self , x ): s = 0 while x > 0 : s += self . c [ x ] x -= BinaryIndexedTree . lowbit ( x ) return s class Solution : def reversePairs ( self , nums : List [ int ]) -> int : s = set () for num in nums : s . add ( num ) s . add ( num * 2 ) alls = sorted ( s ) m = { v : i for i , v in enumerate ( alls , 1 )} ans = 0 tree = BinaryIndexedTree ( len ( m )) for num in nums [:: - 1 ]: ans += tree . query ( m [ num ] - 1 ) tree . update ( m [ num * 2 ], 1 ) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem