How Many Numbers Are Smaller Than The Current Number - Leetcode Solution

Problem Statement:

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.

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]

Approach:

We need to count the number of elements that are smaller than the current element. We can approach the problem in a brute force manner by using two loops, one to iteratively take each element and the other to compare it with all other elements to count the numbers smaller than it. This approach will have a time complexity of O(N^2), which is not efficient. Therefore, we will use a better approach.

An optimal solution to this can be achieved by using a hash table to store the counts of the elements. We will traverse the array and increment the count of each element in the hash table. Then, we will traverse the array again and for each element, we can iterate over all the keys in the hash table that are smaller than the element and add their counts. Finally, we return the list of counts of the smaller numbers.

Algorithm:

1. Initialize an empty hash table
2. Traverse through the array and increment the count of each element in the hash table
3. Traverse through the array once again and for each element, calculate the count of elements smaller than it using the hash table
4. Append the count of smaller elements to a new list
5. Return the list of counts

Python Code:

class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: # count will store the count of each number in the array count = {}

    #iterate through the array once and count the occurrence of each number
    for num in nums:
        if num not in count:
            count[num] = 1
        else:
            count[num] += 1
    
    # iterate through the array and calculate the count of smaller numbers
    smaller_count = [0] * len(nums)
    for i, num in enumerate(nums):
        smaller_count[i] = sum(count[n] for n in count if n < num)
    
    return smaller_count

Time Complexity: O(n + klogk), where n is the length of nums and k is the range of values (0 <= nums[i] <= 100).

Space Complexity: O(k), as hash table will take only k keys where 0 <= nums[i] <= 100.

1