Count smaller elements on the right side of an array in C++

In this tutorial, we will learn to count smaller elements on the right side of an array in C++. We will write a function to count elements which are smaller than the current element that is on the right side.

The rightmost element will return 0.

For Example:

• Input: array= {12, 5, 2, 3, 0, 11, 3}
  Output: {6, 4, 1, 1, 0, 1, 0}
• Input:array=  {5, 4, 3, 2, 1}
  Output: {4, 3, 2, 1, 0}
• Input: array= {1, 2, 3, 4, 5}
  Output:  {0, 0, 0, 0, 0}

Now, we will go for a simple solution. Below is the approach for the solution.

Approach:

• Firstly, initialize all the count of the array as zero.
• Now, we will use two for loops.
• Then the outer for loop will pick the elements from left to right.
• Now, the inner for loop will iterate through all the elements which are at the right of the current element.
• Then check for the condition if it is smaller or not.
• Finally, update the array.
• The time complexity of the given approach is O(n^2).
• Moreover, the auxiliary space is O(1).

You may also like:
Minimum Spanning Tree for Graph in C++

Count smaller elements on the right side in C++

Hence, below is the implementation of this simple approach.

Code:

#include<iostream>
using namespace std;
void constructsmaller (int *array[], int *smaller, int nh) 
{ 
int i, j; 

// initializ the counts
for (i = 0; i < nh; i++) 
  smaller[i] = 0; 

for (i = 0; i < nh; i++) 
{ 
  for (j = i+1; j < nh; j++) 
  { 
  if (array[j] < array[i]) 
    smaller[i]++; 
  } 
} 
} 

// Utility function that will print
void printit(int array[], int seze) 
{ 
int i; 
for (i=0; i < seze; i++) 
  cout<< arr[i]; 

    cout<<"\n"; 
} 

//the main function
//use maloc function
int main() 
{ 
int array[] = {12, 8,14, 1, 3, 30, 6, 4, 0, 2}; 
int nh = sizeof(array)/sizeof(array[0]); 
int *lwer = (int *)malloc(sizeof(int)*n); 
constructsmaller(array, lwer, nh); 
printit(lwer, nh); 
return 0; 
} 

Output Explanation:

INPUT: array={12,8,14,1,3,30,6,4,0,2}
OUTPUT: {7,6,6,1,2,4,3,2,0,0}