How Many Numbers Are Smaller Than the Current Number

Difficulty: Easy | Acceptance: 87.40% | Paid: No Topics: Array, Hash Table, Sorting, Counting Sort

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.

• Examples
• Constraints
• Brute Force
• Sorting
• Counting Sort

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]

Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Constraints

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

Brute Force

Intuition For every number in the array, iterate through the entire array and count how many numbers are strictly smaller than the current number.

Steps

• Initialize an empty result array.
• Loop through each element nums[i] in the array.
• For each nums[i], initialize a counter to 0.
• Loop through every element nums[j] in the array.
• If nums[j] < nums[i], increment the counter.
• Append the counter to the result array.
• Return the result array.

class Solution:
    def smallerNumbersThanCurrent(self, nums: list[int]) -> list[int]:
        res = []
        for i in range(len(nums)):
            count = 0
            for j in range(len(nums)):
                if nums[j] < nums[i]:
                    count += 1
            res.append(count)
        return res

Complexity

• Time: O(n²) where n is the length of the array.
• Space: O(1) if we exclude the output array, otherwise O(n).
• Notes: Simple to implement but inefficient for large inputs.

Sorting

Intuition If we sort the array, the index of an element corresponds to the number of elements smaller than it. We can use a hash map to store the first occurrence index of each unique number to handle duplicates.

Steps

• Create a copy of the original array and sort it.
• Initialize a hash map.
• Iterate through the sorted array. If a number is not already in the map, add it with its current index as the value. This ensures we store the index of the first occurrence (smallest index).
• Iterate through the original array. For each number, look up its value in the map and append it to the result array.
• Return the result array.

class Solution:
    def smallerNumbersThanCurrent(self, nums: list[int]) -> list[int]:
        sorted_nums = sorted(nums)
        mapping = {}
        for i, val in enumerate(sorted_nums):
            if val not in mapping:
                mapping[val] = i
        return [mapping[num] for num in nums]

Complexity

• Time: O(n log n) due to the sorting step.
• Space: O(n) to store the sorted array and the hash map.
• Notes: More efficient than brute force, but modifies the order (via copy) and requires extra space.

Counting Sort

Intuition Given the constraint 0 <= nums[i] <= 100, the range of values is small. We can use counting sort (frequency array) to count occurrences of each number. Then, we calculate the prefix sum to determine how many numbers are smaller than a specific value.

Steps

• Initialize a frequency array count of size 101 with zeros.
• Iterate through nums and increment the count for each number.
• Transform the count array into a prefix sum array where count[i] represents the number of elements less than or equal to i. This is done by adding count[i-1] to count[i] for i from 1 to 100.
• Initialize the result array.
• Iterate through nums. For each number num, the number of smaller elements is count[num-1] if num > 0, otherwise 0.
• Return the result array.

class Solution:
    def smallerNumbersThanCurrent(self, nums: list[int]) -> list[int]:
        count = [0] * 101
        for num in nums:
            count[num] += 1
        for i in range(1, 101):
            count[i] += count[i - 1]
        res = []
        for num in nums:
            if num == 0:
                res.append(0)
            else:
                res.append(count[num - 1])
        return res

Complexity

• Time: O(n + k) where n is the number of elements and k is the range of values (101).
• Space: O(k) for the frequency array.
• Notes: The most optimal approach for this problem given the constraints.