Count Numbers Smaller Than Current

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Given an array of integers, for each element, count how many elements in the array are strictly smaller than it. Return an array of these counts.

Examples:

Input: [8,1,2,2,3]

Output: [4,0,1,1,3]

Explanation: For 8, four numbers (1,2,2,3) are smaller; for 1, no number is smaller; for each 2, one number (1) is smaller; for 3, three numbers (1,2,2) are smaller.

Input: [6,5,4,3,2,1]

Output: [5,4,3,2,1,0]

Input: [1,2,3]

Output: [0,1,2]

Constraints

2 ≤ array length ≤ 100
0 ≤ each element ≤ 1000

Editorial

Intuition:

The constraints are small (array length ≤ 100, values ≤ 1000), allowing a frequency-based approach. By counting occurrences of each number and using prefix sums, we can answer the count of smaller numbers for any value in constant time.

Approach:

Create a frequency array of size 1001 (indices 0–1000) and count occurrences of each number in the input.
Build a prefix sum array where prefix[i] stores the total count of numbers strictly less than i. Compute as prefix[i] = prefix[i-1] + freq[i-1] for i from 1 to 1000.
For each element in the original array, the result for that element is prefix[num], which gives the number of smaller elements.

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> freq(1001, 0);
        for (int num : nums) freq[num]++;
        vector<int> prefix(1001, 0);
        for (int i = 1; i <= 1000; ++i) 
            prefix[i] = prefix[i-1] + freq[i-1];
        vector<int> result;
        for (int num : nums) 
            result.push_back(prefix[num]);
        return result;
    }
};
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] freq = new int[1001];
        for (int num : nums) freq[num]++;
        int[] prefix = new int[1001];
        for (int i = 1; i <= 1000; i++) 
            prefix[i] = prefix[i-1] + freq[i-1];
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) 
            result[i] = prefix[nums[i]];
        return result;
    }
}
from typing import List

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        freq = [0] * 1001
        for num in nums:
            freq[num] += 1
        prefix = [0] * 1001
        for i in range(1, 1001):
            prefix[i] = prefix[i-1] + freq[i-1]
        return [prefix[num] for num in nums]
var smallerNumbersThanCurrent = function(nums) {
    let freq = new Array(1001).fill(0);
    for (let num of nums) freq[num]++;
    let prefix = new Array(1001).fill(0);
    for (let i = 1; i <= 1000; i++) 
        prefix[i] = prefix[i-1] + freq[i-1];
    let result = [];
    for (let num of nums) 
        result.push(prefix[num]);
    return result;
};

Complexity Analysis:

Time Complexity: O(n + m), where n is the array length (≤ 100) and m is the maximum value (1000). Since m is constant, the time is effectively O(n).

Space Complexity: O(m) for the auxiliary arrays (size 1001). Because m is fixed, this is O(1) extra space (excluding the output array).

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories