How many numbers are smaller than the current number

Array Hash Table Sorting Counting Sort

87.4% acceptance

Feb 25, 2026

5993

158

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i]. Return the answer in an array.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn smaller_numbers_than_current(nums: Vec<i32>) -> Vec<i32> {
    let mut count = [0i32; 102];
    for &x in &nums { count[x as usize + 1] += 1; }
    // prefix sum
    for i in 1..102 { count[i] += count[i-1]; }
    nums.iter().map(|&x| count[x as usize]).collect()
  }
}