You are given an Array of integers and you need to find out the total number of elements which are smaller then the current element in the whole array.
Examples :
Input : arr[] = {12, 1, 2, 3, 0, 11, 4}
Output : countSmaller[] = {6, 1, 2, 3, 0, 5, 4}
Input : arr[] = {10, 10, 10, 10}
Output : countSmaller[] = {0, 0, 0, 0}
Approach :
- First of all store the original array in a temporary array and sort the temporary array.
- Now as we have the sorted array we use the lower_bound (in-built function) to find the lower bound of each and every element of the original array in the temporary array.
- And that lower bound value is going to be the number of elements less that it in the whole array .
Implementation :
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of smaller elements
vector<int> countSmaller(vector<int>& arr, int n)
{
// taking a temp array to store the original array
vector<int> temp = arr;
// sorting the temp array
sort(temp.begin(), temp.end());
vector<int> countsmaller;
// iterating over the original array
for (int i = 0; i < n; i++) {
// finding the lower bound of the element
// form the original array in the temp array
int pos
= lower_bound(temp.begin(), temp.end(), arr[i])
- temp.begin();
// pushing the obtained value in the countsmaller
// array
countsmaller.push_back(pos);
}
// returning the final array
return countsmaller;
}
int main()
{
vector<int> arr = { 12, 1, 2, 3, 0, 11, 4 };
int n = arr.size();
vector<int> ans = countSmaller(arr, n);
for (auto i : ans)
cout << i << " ";
}
Time Complexity : O(n*log n), as we have used sorting
Space Complexity : O(n), as we are using the temp array