1365. Count Of Numbers That Are Smaller Than the Current Number

The solution to LeetCode easy problem

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

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

Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Constraints:

• 2 <= nums.length <= 500
• 0 <= nums[i] <= 100

Let us first understand what the question says. Taking nums = [8,1,2,2,3] ans the example. In this how many elements are smaller than 8? It is simple, 1, 2, 2,3 which counts to a total of 4, similarly for 1 it is 0, for 2 it is 1 and for 3 it is 3. So now the total count answer = [4,0,1,1,3]

I hope this is clear to you. Now let us try different approaches to solve this question.

1. Brute Force Solution

So how can we solve this question? For every element in the array, I can loop over the leftover array and count the number of elements in the array satisfying the given condition.

In this solution, we will have a simple approach of going through two loops I and j, and counting the number of elements satisfying the given condition in the question.

For every element, I will traverse the whole array once to find elements satisfying the condition and then I will push back the total count for each element satisfying the condition.

Time Complexity — O(n*n)

Space Complexity-O(n) because I am using a vector to store the count of elements satisfying the given condition for each element.

This is a simple approach and you can easily do a dry run of the given code below.

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

2. Optimized Approach

Now here I will try to optimize the above time complexity. Yes, there is, let us discuss how.

Let us try to understand the intuition behind the solution using the given code below :

nums = [8,1,2,2,3] , n = 5 , snum = [8,1,2,2,3]

after sorting , snum = [1,2,2,3,8]

mp[snum[4]] = mp[8] = 4

mp[snum[3]] = mp[3] = 3

mp[snum[2]] = mp[2] = 2

mp[snum[1]] = mp[2] = 1(This value will be overwritten to 1 and not 2)

mp[snum[0]] = mp[1] = 0

This is sorting the array and then each index will tell you how many elements are smaller than the element at that index.

Now, nums[0] = mp[nums[0]] = mp[8] = 4

nums[1] = mp[nums[1]] = mp[1] = 0

nums[2] = mp[nums[2]] = mp[2] = 1

nums[3] = mp[nums[3]] = mp[2] = 1

nums[4] = mp[nums[4]] = mp[3] = 3

So now our final answer is [4,0,1,1,3].

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        map<int,int>mp;
        int n = nums.size();
        vector<int>snum = nums;
        
        sort(snum.begin(),snum.end());
        for(int i=n-1;i>=0;i--)
        {
            mp[snum[i]]=i;
        }
        
        for(int i=0;i<n;i++)
            nums[i] = mp[nums[i]];
        
        return nums;
    }
};

The approach involved in this is that we first sort a copy of the given vector. Sorting the elements puts them in a position where it satisfies the given condition. And the second time we simply store the value of the elements greater than it in the nums (original array) itself.

I would urge you to do a dry run of the above-given code and find out yourself how the logic evolves behind the intuition of the solution.

Time Complexity — O(nlogn) + O(n) +O(n) = O(nlogn) where nlogn for sorting, n for traversing the vector two times.

Space Complexity — O(n) + O(n) = O(n) where n for storing the vector and a map.

……………………………………………………………………………………….

Hope this helps! Stay tuned for more, till then keep coding!!

Remember consistency is the key!!!!💻🙌

Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati ☕

Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer