How Many Numbers Are Smaller Than the Current Number

Find the number of elements that are smaller than the current element for each element in the 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).  

Approach 1 :

Java

import java.util.Arrays;

import java.util.HashMap;

public class SmallerNumbersThanCurrent {

    public static void main(String[] args) {

        int nums[] = { 1, 2, 6, 7, 0, 0, 9 };

        int a[] = smallerNumbersThanCurrent(nums);

        System.out.println(Arrays.toString(a));

    }

    public static int[] smallerNumbersThanCurrent(int[] nums) {

        // create new array and hold value

        int a[] = new int[nums.length];

        // assign value to new array

        for (int i = 0; i < a.length; i++) {

            a[i] = nums[i];

        }

        // create hashmap

        HashMap<Integer, Integer> map = new HashMap<>();

        // sort the given array

        Arrays.sort(nums);

        // iterate till end

        for (int i = 0; i < nums.length; i++) {

            // if not contain then add

            if (!map.containsKey(nums[i]))

                map.put(nums[i], i);

        }

        // map to array

        for (int i = 0; i < a.length; i++) {

            a[i] = map.get(a[i]);

        }

        return a;

    }

}

C++ 

#include <bits/stdc++.h>

using namespace std;

//function to count the number 

//of smaller elements then current element

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 

{

    vector<int> res;

     int max1=nums[0],min1=nums[0];

     //find the maximum elemeent

     //and minimum element in the array

    for(int i=0;i<nums.size();i++)

      {

          if(nums[i]>max1)

                max1=nums[i];

          else if(nums[i]<min1)

                min1=nums[i];

      }

    //create an array of size maximum element+1

    int freq[max1+1]={0};

    //count frequency of each element

    for(int i=0;i<nums.size();i++)

         freq[nums[i]]++;

    

    //count number of elements which are less than

    //the current elements

     for(int i=0;i<nums.size();i++)

     {  

         int cnt=0;

         for(int j=min1;j<nums[i];j++)

          {

             if(freq[j]>0)

                 cnt+=freq[j];

          }

        res.push_back(cnt);

     }

        return res;

}

int main()

{

  vector<int> nums={8,1,2,2,3};

  vector<int> small=smallerNumbersThanCurrent(nums);

  for(int i=0;i<small.size();i++)

     cout<<small[i]<<" ";

  return 0;

}

//Time Complexity:O(n^2)

Approach 2:  Binary search (lower_bound)

C++

#include <bits/stdc++.h>

using namespace std;

vector<int> smallerNumbersThanCurrent(vector<int>& nums)

{

    //create a dummy array

     vector<int> dummy(nums.begin(),nums.end());

     //sort the dummy array

     sort(dummy.begin(),dummy.end());

     vector<int> res;

    //itearte for all elemenst

    for(int i=0;i<nums.size();i++)

    {

        int lower=lower_bound(dummy.begin(),dummy.end(),nums[i])

                -dummy.begin();

        res.push_back(lower);

    }

        return res;

}

int main()

{

  vector<int> nums={8,1,2,2,3};

  vector<int> small=smallerNumbersThanCurrent(nums);

  for(int i=0;i<small.size();i++)

     cout<<small[i]<<" ";

  return 0;

}

//Time Complexity:O(nlog(n))