Count smaller elements for every element of an array

Updated

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 :

  1. First of all store the original array in a temporary array and sort the temporary array.
  2. 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.
  3. 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 << " ";
}

Output :

6 1 2 3 0 5 4

Time Complexity : O(n*log n), as we have used sorting

Space Complexity : O(n), as we are using the temp array

Comment
Mithlesh Upadhyay Published 22 Nov 2026 · 2 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials