Count of Smaller Numbers After Self in C++

Suppose we have an array nums, we have to find another array called count, in this count array, the count[i] stores the number of smaller elements to the right of nums[i].

So if the input is like: [5,2,7,1], then the result will be [2,1,1,0].

To solve this, we will follow these steps −

• Define one method called update(), this will take index, array bit and n

• while index <= n, do −

  • increase bit[index]

  • index = index + (index) AND ( - index)

• Define one array called query(), this will take index and bits array

  • ans := 0

  • while index > 0, do −

    • ans = ans + bit[index]

    • index = index – (index AND - index)

  • return ans

• From the main method, do the following −

• n := size of nums

• Define an array res of size n

• if (n is non-zero) is false, then, return res

• maxx := 0, minn = nums [0]

• for initializing i := 1, when i < n, increase i by 1 do −

  • minn := min of nums[i] and minn

• for initializing i := 0, when i < n, increase i by 1 do −

  • nums[i] := nums[i] - minn + 1

  • maxx := max of nums[i] and maxx

• Define an array bit of size maxx + 1

• for initializing i := n - 1, when i >= 0, decrease i by 1 do −

  • num = nums[i] – 1

  • x := Call the function query(num,bit)

  • res[i] := x

  • Call the function update(num + 1, bit, maxx)

• return res

Example

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } class Solution {    public:    void update(int index,vector <int>& bit, int n){       while(index<=n){          bit[index]++;          index += (index)&(-index);       }    }    int query(int index, vector <int> bit){       int ans = 0;       while(index>0){          ans+=bit[index];          index -= index&(-index);       }       return ans;    }    vector<int> countSmaller(vector<int>& nums) {       int n = nums.size();       vector <int> res(n);       if(!n)return res;       int maxx = 0;       int minn = nums[0];       for(int i =1;i<n;i++)minn = min(nums[i],minn);       for(int i =0;i<n;i++){          nums[i] = nums[i]-minn+1;          maxx = max(nums[i],maxx);       }       vector <int> bit(maxx+1);       for(int i =n-1;i>=0;i--){          int num = nums[i]-1;          int x = query(num,bit);          res[i] = x;          update(num+1,bit,maxx);       }       return res;    } }; main(){    Solution ob;    vector<int> v = {5,2,7,1};    print_vector(ob.countSmaller(v)); }

Input

[5,2,7,1]

Output

[2, 1, 1, 0, ]