Home Arrays [Leetcode] – Numbers Smaller than current

[Leetcode] – Numbers Smaller than current

by nikoo28
0 comment 4 mins read

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).

Fig: Sample test cases

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.

Fig: Compare each element with the rest of the array

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.

Fig: Frequency Array

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.

Fig: Populating the counts

Once we iterate through the entire array, we get a count of each of the elements.

Fig: Bucket values representing counts

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.

Fig: Smaller count to left, and larger count to right

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:

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More