1365. How Many Numbers Are Smaller Than the Current Number.cpp

// 1365. How Many Numbers Are Smaller Than the Current Number
// Solved
// Easy
// Topics
// Companies
// Hint
// 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

// Seen this question in a real interview before?
// 1/5
// Yes
// No
// Accepted
// 601.9K
// Submissions
// 691.9K
// Acceptance Rate
// 87.0%
// Topics
// Companies
// Hint 1
// Hint 2
// Similar Questions
// Discussion (34)

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int>sortedNums=nums;
        sort(sortedNums.begin(),sortedNums.end());
        unordered_map<int,int>small;
        for(int i=0;i<sortedNums.size();i++){
            if(small.find(sortedNums[i])==small.end()){
                small[sortedNums[i]]=i;
            }
        }
        vector<int>res;
        for(int num:nums){
            res.push_back(small[num]);
        }
        return res;
    }
};