Reverse Pairs

HARD

Description

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

Checkout 2 different approaches to solve Reverse Pairs. Click on different approaches to view the approach and algorithm in detail.

Brute Force

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.

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.

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++) {
                if ((long) nums[i] > 2 * (long) nums[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we only use a constant amount of extra space for the counter and loop indices.

Pros and Cons

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).

Code Solutions

Checking out 3 solutions in different languages for Reverse Pairs. Click on different languages to view the code.

class Solution {
public
  int reversePairs(int[] nums) {
    TreeSet<Long> ts = new TreeSet<>();
    for (int num : nums) {
      ts.add((long)num);
      ts.add((long)num * 2);
    }
    Map<Long, Integer> m = new HashMap<>();
    int idx = 0;
    for (long num : ts) {
      m.put(num, ++idx);
    }
    BinaryIndexedTree tree = new BinaryIndexedTree(m.size());
    int ans = 0;
    for (int i = nums.length - 1; i >= 0; --i) {
      int x = m.get((long)nums[i]);
      ans += tree.query(x - 1);
      tree.update(m.get((long)nums[i] * 2), 1);
    }
    return ans;
  }
} class BinaryIndexedTree {
private
  int n;
private
  int[] c;
public
  BinaryIndexedTree(int n) {
    this.n = n;
    c = new int[n + 1];
  }
public
  void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += lowbit(x);
    }
  }
public
  int query(int x) {
    int s = 0;
    while (x > 0) {
      s += c[x];
      x -= lowbit(x);
    }
    return s;
  }
public
  static int lowbit(int x) { return x & -x; }
}

Video Solution

Watch the video walkthrough for Reverse Pairs

Algorithms:

Binary SearchDivide and ConquerMerge Sort

Data Structures:

ArrayBinary Indexed TreeSegment TreeOrdered Set