According to the given problem statement, you are given an array of integers. We need to output a resultant array that tells how many number are smaller than the current number from the entire array.
Let us look at some sample test cases:
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).
Input: nums = [ 6 , 5 , 4 , 8 ]
Output: [ 2 , 1 , 0 , 3 ]
Explanation:
For nums[0]=6 there exist 2 smaller numbers than it (5 and 4).
For nums[1]=5 there exist one smaller number than it (4).
For nums[2]=4 does not exist any smaller number than it.
For nums[3]=8 there exist 3 smaller number than it (6, 5 and 4).
Brute Force Method:
A very direct method to find the count of smaller numbers than the current will be to take up each number one by one and compare it with all the rest one by one.
- Start from the first element.
- Compare it with each of the other element in the array and keep a count.
- Record the count and move to the next element.
- Repeat the steps for the second element and do it for all the elements.
At the end we will have a resultant array with the count of smaller numbers.
Time Efficient Method:
In the above method, we are facing a problem because of the time the process takes. Hence, to find an efficient solution we try to make sure that we are not iterating through the array again and again. One idea is that we have to “count” the number of smaller elements
Counting sort can be helpful in such a scenario.
For a given array like [ 8, 1, 2, 2, 3, 5, 2, 6, 1, 5], we can initialize a frequency array that will store the count of each element.
Iterate through the array, and keep on incrementing the counts in the frequency array. Once we have iterated through the array, we know exactly how many 1's we have in the array, how many 2's we have, and so on.
Once we iterate through the entire array, we get a count of each of the elements.
Look at any element now. For example, if we look at element 2, to its left we have 2 elements (1, 1) and towards its right we have 5 elements (3, 5, 5, 6, 8). In this particular problem we need to count the numbers smaller than the current number.
This gives away the solution, a count of all the numbers to the left will give the correct answer.
Code:
public int[] smallerNumbersThanCurrent(int[] nums) {
// Create buckets for counting sort
int[] buckets = new int[102];
// Get frequency of each element
for (int num : nums) {
buckets[num]++;
}
// Count smaller numbers than each element
for (int i = 1; i < buckets.length; i++) {
buckets[i] += buckets[i - 1];
}
// Populate the result
int[] result = new int[nums.length];
for (int i = 0; i < result.length; i++) {
if (nums[i] == 0)
result[i] = 0;
else
result[i] = buckets[nums[i] - 1];
}
return result;
}
Code language: Java (java)Time Complexity: O(n)
Space Complexity: O(n)
You can also find the code and test cases on GitHub.
Video Explanation:
