How Many Numbers Are Smaller Than the Current Number

Easy
188.

How Many Numbers Are Smaller Than the Current Number

How Many Numbers Are Smaller Than the Current Number is an easy coding problem on arrays, hash table and counting sort, asked in Amazon, Google and Adobe interviews.

Given the array nums, for each nums[i] count how many numbers in the array are strictly smaller than it.

Return the answer as an array in the same order as the input.

Example 1

Input
nums = [8,1,2,2,3]
Output
[4,0,1,1,3]
Explanation
For 8 there are four smaller values; for 1 there are none; for each 2 only the 1 is smaller.

Example 2

Input
nums = [6,5,4,8]
Output
[2,1,0,3]

Example 3

Input
nums = [7,7,7,7]
Output
[0,0,0,0]
Explanation
Strictly smaller, so equal values do not count.

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 100

Follow-up: The values are bounded by 100. Can you answer every query in O(1) after O(n + 100) preprocessing?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

How Many Numbers Are Smaller Than the Current Number Solution

How Many Numbers Are Smaller Than the Current Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

How Many Numbers Are Smaller Than the Current Number is an easy coding problem on arrays, hash table and counting sort, asked in Amazon, Google and Adobe interviews.

Problem statement

Given the array nums, for each nums[i] count how many numbers in the array are strictly smaller than it.

Return the answer as an array in the same order as the input.

Example 1

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: For 8 there are four smaller values; for 1 there are none; for each 2 only the 1 is smaller.

Example 2

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3

Input: nums = [7,7,7,7]
Output: [0,0,0,0]
Explanation: Strictly smaller, so equal values do not count.

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 100

Follow-up: The values are bounded by 100. Can you answer every query in O(1) after O(n + 100) preprocessing?

Hints for How Many Numbers Are Smaller Than the Current Number

  1. Hint 1

    The nested-loop count is O(n²) and passes at this size, but the bounded range invites something better.

  2. Hint 2

    Tally how many times each value 0…100 occurs, then take a prefix sum of those tallies.

  3. Hint 3

    prefix[v - 1] is then exactly how many elements are strictly below v.

How to solve How Many Numbers Are Smaller Than the Current Number

Values are bounded by 100, so tally them and take a prefix sum: prefix[v] then equals the number of elements strictly below v.

Approach

  1. Tally with an offset: count[x + 1] += 1.
  2. Prefix-sum the tally so count[v] holds how many values are < v.
  3. Map each x to count[x].

Why it works

After the shift, count[v] sums the frequencies of 0..v-1, which is precisely the count of strictly smaller elements.

Complexity

  • Time — O(n + 100)
  • Space — O(100)

Pitfalls

  • The + 1 offset is what makes the comparison strict; without it you count <=.
  • The O(n²) double loop passes but is not the intended solution.

Reference solution

Python

def smallerNumbersThanCurrent(nums):
    count = [0] * 102
    for x in nums:
        count[x + 1] += 1
    for v in range(1, 102):
        count[v] += count[v - 1]
    return [count[x] for x in nums]

Java

public static int[] smallerNumbersThanCurrent(int[] nums) {
    int[] count = new int[102];
    for (int x : nums) count[x + 1]++;
    for (int v = 1; v < 102; v++) count[v] += count[v - 1];
    int[] out = new int[nums.length];
    for (int i = 0; i < nums.length; i++) out[i] = count[nums[i]];
    return out;
}

C++

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    vector<int> count(102, 0);
    for (int x : nums) count[x + 1]++;
    for (int v = 1; v < 102; v++) count[v] += count[v - 1];
    vector<int> out;
    for (int x : nums) out.push_back(count[x]);
    return out;
}

JavaScript

var smallerNumbersThanCurrent = function(nums) {
    const count = new Array(102).fill(0);
    for (let i = 0; i < nums.length; i++) count[nums[i] + 1]++;
    for (let v = 1; v < 102; v++) count[v] += count[v - 1];
    const out = [];
    for (let i = 0; i < nums.length; i++) out.push(count[nums[i]]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets