How Many Numbers Are Smaller Than the Current Number Leetcode Solution

Table of Contents

Problem Statement

In this problem, we are given an array. For each element of this array, we have to find out the number of elements smaller than that element.
i.e. for each i (0<=i<arr.length) we have to find out count of elements less than the number arr[i]. For that we have to return an answer array.

Example

nums = [8,1,2,2,3]

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

nums = [6,5,4,8]

[2,1,0,3]

Approach (Brute Force)

We can simply run a loop for every element, starting from left to right.
For each element, we will find the count of the elements which are lesser than the current number.
So basically, we run one outer loop for each element and in inner loop, we will traverse the whole array to count every element less than current value.

Implementation for How Many Numbers Are Smaller Than the Current Number Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
{
    vector<int> ans;

    for(int i=0;i<nums.size();i++)
    {
        int val=nums.at(i),count=0;
        for(int j=0;j<nums.size();j++)
        {
            if(nums.at(j)<val)  count++;
        }
        ans.push_back(count);
    }

    return ans;
}

int main() 
{
    vector<int> nums{ 8 , 1, 2 , 2 , 3 }; 
    vector<int> ans=smallerNumbersThanCurrent(nums);
    
    for(auto val:ans) cout<<val<<" ";
    cout<<endl;
    
    return 0;  
}

4 0 1 1 3

Java Program

import java.lang.*;

class Rextester
{  
    public static int[] smallerNumbersThanCurrent(int[] nums) 
    {
        int[]ans=new int[nums.length];

        for(int i=0;i<nums.length;i++)
        {
            int count=0;
            for(int j=0;j<nums.length;j++)
            {
                if(nums[i]>nums[j])   count++;
            }
            ans[i]=count;
        }

        return ans;
    }
    
    public static void main(String args[])
    {
       int[]nums={8,1,2,2,3};  
       int[]ans=smallerNumbersThanCurrent(nums);
        
       for(int num:ans)  
       {
           System.out.print(num+" ");
       }
        
    }
}

4 0 1 1 3

Complexity Analysis for How Many Numbers Are Smaller Than the Current Number Leetcode Solution

Time Complexity

O(n^2) : We are using nested loop each running for n lengths. Hence time complexity will be O(n^2).

Space Complexity

O(1) : We have just used an array of length n to return the answer. Beside this we have not used any extra memory. So space complexity is constant.

Approach (Optimized)

As we know that number smaller than any element in an array is equal to count of number less than or equal to that number-1.
Like, in array
1 2 3 4 4 5
count of numbers less than 5 is count of numbers less than or equal to 4.
So, if we somehow store the count of every element present in the given array, then we can easily say that how many elements are less than it.

How Many Numbers Are Smaller Than the Current Number Leetcode Solution

So, we are keeping a count array of size 101. (because the number may be between [0,100])
every index of count array i will say the occurrence of number i in the given array.

Now, to know how many numbers are less than or equal to a number at a position, we have to apply prefix sum.
so, we will apply prefix sum on count array.

Then for each element i of the array, number of elements less than this number will be count[i-1].

So, in this approach firstly we will create our count array.
Then we will convert it into the prefix sum.
Then for each element num of input array we will have count[num-1].