Count of smaller numbers after self

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

43.3% acceptance

Jan 12, 2026

9231

252

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_smaller(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let mut result = vec![0; n];
    let mut indices: Vec<usize> = (0..n).collect();
    
    fn merge_sort(nums: &[i32], indices: &mut [usize], result: &mut [i32], start: usize, end: usize) {
      if start >= end {
        return;
      }
      
      let mid = start + (end - start) / 2;
      merge_sort(nums, indices, result, start, mid);
      merge_sort(nums, indices, result, mid + 1, end);
      
      let mut temp = Vec::new();
      let mut i = start;
      let mut j = mid + 1;
      let mut count = 0;
      
      while i <= mid && j <= end {
        if nums[indices[j]] < nums[indices[i]] {
          temp.push(indices[j]);
          count += 1;
          j += 1;
        } else {
          result[indices[i]] += count;
          temp.push(indices[i]);
          i += 1;
        }
      }
      
      while i <= mid {
        result[indices[i]] += count;
        temp.push(indices[i]);
        i += 1;
      }
      
      while j <= end {
        temp.push(indices[j]);
        j += 1;
      }
      
      for (k, &idx) in temp.iter().enumerate() {
        indices[start + k] = idx;
      }
    }
    
    if n > 0 {
      merge_sort(&nums, &mut indices, &mut result, 0, n - 1);
    }
    result
  }
}