Pankaj Tanwar
Published on

How Many Numbers Are Smaller Than the Current Number.

––– views

Problem of the day - How Many Numbers Are Smaller Than the Current Number.

Tag - Easy.

Its' third day of my coding diary. Problem for today seems pretty easy - peasy but let's see if I can solve it or not.

So, the problem for the day is, an array is given. The result should be an array, with the count of how many numbers are smaller than the current number.

As usual, my first thought, run loop twice to find result count (numbers less then the current number) of each number. Pretty easy to code!

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> res;
        int count = 0;
        for(int i=0;i<nums.size();i++) {
            count = 0;
            for(int j=0;j<nums.size();j++) {
                if(nums[i] > nums[j]) count++;
            }
            res.push_back(count);
        }
        return res;
    }
};

Ahh, well. It's very slow.

Time Complexity - O(n2)

Space Complexity - O(n)

Let me find some more optimized approach. What else can I do here? Why not just sort the array, iterate over the array to find count for each number and store that in a hashmap. Isn't it taking much space? Let's leave it for now.

Now, my optimized code looks like this -

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> res(nums);
        sort(nums.begin(), nums.end());


        map<int,int> hash;


        for(int i=1;i<nums.size();i++) {
            if(nums[i] != nums[i-1]) {
                hash[nums[i]] = i;
            }
        }


        for(int i=0;i<res.size();i++) {
            res[i] = hash[res[i]];
        }


        return res;
    }
};

Seems good.

Time Complexity - O(n logn)

Space Complexity - O(n)

But I was still not happy by this. I was still having a feeling of some more optimized approach possible. Well, I tried to find it out but couldn't find one. I went through the leetcode discussion tab and selected filter c++ for top voted answers.

A really good approach by OzodTagoev helped me crack this.

It taught me to keep an eye on constraints as it can help a lot in deciding the optimized approach. Here, its given that, max possible value in array can be 100. So why not keep an array of length 100 to and store count there as per the index.

Well, oops. it's very late anyway and I am not in the mood of explaining the approach. Here is my code -

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> res(101,0);


        for(auto val: nums) res[val]++;


        for(int i=1;i<101;i++) {
            res[i] += res[i-1];
        }


        vector<int> ans;
        for(int i=0;i<nums.size();i++) {
            if(nums[i] == 0) {
                ans.push_back(0);
            } else {
                ans.push_back(res[nums[i]-1]);
            }
        }
        return ans;




    }
};

Time Complexity - O(n)

Space Complexity - O(n)

So tip for the day, constraints are very important.

You might like previous editions of my coding diary -

Tweet this article