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:**

1 2 3 4 5 6 7 8 | 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:**

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

**Example 3:**

1 2 | Input: nums = [7,7,7,7] Output: [0,0,0,0] |

**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 n^{2} 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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int[] copy = nums.clone(); Arrays.sort(copy); HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int smaller = 0; for(int i: copy){ if(!map.containsKey(i)){ map.put(i,smaller); } smaller++; } for (int i=0; i<nums.length; i++){ nums[i] = map.get(nums[i]); } return nums; } } |

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 🙂