Reverse pairs

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

33.7% acceptance

Jan 13, 2026

6964

297

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

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn reverse_pairs(mut nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut temp = vec![0; n];
    Self::merge_sort(&mut nums, 0, n, &mut temp)
  }
  
  fn merge_sort(nums: &mut [i32], left: usize, right: usize, temp: &mut [i32]) -> i32 {
    if right - left <= 1 { return 0; }
    let mid = left + (right - left) / 2;
    let mut count = Self::merge_sort(nums, left, mid, temp) + Self::merge_sort(nums, mid, right, temp);
    
    let mut j = mid;
    for i in left..mid {
      while j < right && nums[i] as i64 > 2 * nums[j] as i64 {
        j += 1;
      }
      count += (j - mid) as i32;
    }
    
    Self::merge(nums, left, mid, right, temp);
    count
  }
  
  fn merge(nums: &mut [i32], left: usize, mid: usize, right: usize, temp: &mut [i32]) {
    let (mut i, mut j, mut k) = (left, mid, left);
    while i < mid && j < right {
      if nums[i] <= nums[j] {
        temp[k] = nums[i];
        i += 1;
      } else {
        temp[k] = nums[j];
        j += 1;
      }
      k += 1;
    }
    while i < mid { temp[k] = nums[i]; i += 1; k += 1; }
    while j < right { temp[k] = nums[j]; j += 1; k += 1; }
    nums[left..right].copy_from_slice(&temp[left..right]);
  }
}