Site icon Study Algorithms

[Leetcode] – Numbers Smaller than current

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.

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:

Exit mobile version