How Many Numbers are Smaller Than the Current Number

Problem Statement

Given the array nums, for each nums[i], return the number of elements in nums that are smaller than it.

Constraints

2 <= nums.length <= 500
0 <= nums[i] <= 100

Examples

Example 1:

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

Explanation: 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

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

Different Approaches

1️⃣ Brute Force Approach (Nested Loops)

For each element, loop through the entire array and count how many numbers are smaller than it.

Code:

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    vector<int> res(nums.size());

    for (int i = 0; i < nums.size(); ++i) {
        int count = 0;
        for (int j = 0; j < nums.size(); ++j) {
            if (nums[j] < nums[i]) count++;
        }
        res[i] = count;
    }

    return res;
}

Complexity Analysis:

• Time Complexity:O(n^2), where n is the length of the array.
• Space Complexity:O(n)

2️⃣ Counting Sort / Frequency Array (Optimized Approach)

Intuition:

Since all value lie in the range 0 to 100, so we can use counting to optimize.

Approach:

1. Count frequency of each number.
2. Build prefix sum array (how many numbers are smaller).
3. Use it to fill the result array.

Code:

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        // Frequency array to count occurrences of each number from 0 to 100
        int frequency[101] = {0};

        // Output vector to store the result
        vector<int> ans(nums.size());

        // Step 1: Count how many times each number appears in the array
        for (int i = 0; i < nums.size(); i++) {
            frequency[nums[i]]++;
        }

        // Step 2: Build prefix sum
        // frequency[i] will now contain count of numbers <= i
        for (int i = 1; i <= 100; i++) {
            frequency[i] = frequency[i] + frequency[i - 1];
        }

        // Step 3: For each number in the original array,
        // get how many numbers are smaller than it using the prefix sum array
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                ans[i] = 0; // No numbers smaller than 0
            } else {
                ans[i] = frequency[nums[i] - 1];
            }
        }

        // Step 4: Return the final result
        return ans;
    }
};

Complexity Analysis:

• Time Complexity:O(n + k), where k = 101
• Space Complexity:O(k) for frequency array