Leetcode 1365: How Many Numbers Are Smaller Than the Current Number

Category : 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.

https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/

Examples

Example 1:

Example 2:

Example 3:

Constraints:

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

Solution Approach

In this question, we have to find how many numbers are smaller than the current number in the array in place i.e we cannot change the position of the element in the array. The brute force solution is very time consuming and it will take n2 time to complete in the worst case, so its complexity is very high. 

Initially, I thought of sorting the array and then printing out the numbers which are smaller than any particular element in that array but that solution has a major disadvantage as the elements will be displaced from the original position which should not happen. There should be a way to clone the array, sort it and then make changes in the original array which I did that with the help of clone and sort functions of the array and also used hashmap in the process.

My approach was simple but intuitive I cloned the initial array and sorted the cloned version. For every unique entry in the cloned array, I stored in the Hashmap with the key being the entry and value of that key is the number of element encountered before that. The smallest element will have the value 0 and it increases with every element encountered in the array given it is unique. If it is not unique then it is not added to the map. 

In the end, I iterated through each element in the initial array and placed the value of the map’s key by comparing the key of the map with the element at each index thus making the in place changing of the array. Then I returned the same array from the function as the solution. 

Solution code

For more Leetcode explained solutions visit Leetcode Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via Contact page I will surely respond. Happy Leetcoding 🙂

Leave a Comment

Your email address will not be published. Required fields are marked *