Count smaller elements on Right side

Given an unsorted array arr[] of distinct integers, construct another array countSmaller[] such that countSmaller[i] contains the count of smaller elements on the right side of each element arr[i] in the array.

Examples:

Input: arr[] = {12, 1, 2, 3, 0, 11, 4}
Output: countSmaller[] = {6, 1, 1, 1, 0, 1, 0}

Input: arr[] = {5, 4, 3, 2, 1}
Output: countSmaller[] = {4, 3, 2, 1, 0}

Input: arr[] = {1, 2, 3, 4, 5}
Output: countSmaller[] = {0, 0, 0, 0, 0}

We strongly recommend that you click here and practice it, before moving on to the solution.

Naive Approach:

Use nested loops. The outer loop picks all elements from left to right. The inner loop iterates through all the elements on right side of the picked element and updates countSmaller[].

Below is the implementation of the above idea.

C++

#include <iostream>
using namespace std;
 
void constructLowerArray(int arr[], int* countSmaller,
                         int n)
{
    int i, j;
 
    // Initialize all the counts in
    // countSmaller array as 0
    for (i = 0; i < n; i++)
        countSmaller[i] = 0;
 
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[i])
                countSmaller[i]++;
        }
    }
}
 
// Utility function that prints
// out an array on a line
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
 
    cout << "\n";
}
 
// Driver code
int main()
{
    int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int* low = (int*)malloc(sizeof(int) * n);
 
    constructLowerArray(arr, low, n);
    printArray(low, n);
 
    return 0;
}
 
// This code is contributed by Hemant Jain

C

void constructLowerArray(int arr[], int* countSmaller,
                         int n)
{
    int i, j;
 
    // initialize all the counts in countSmaller array as 0
    for (i = 0; i < n; i++)
        countSmaller[i] = 0;
 
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[i])
                countSmaller[i]++;
        }
    }
}
 
/* Utility function that prints out an array on a line */
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
 
    printf("\n");
}
 
// Driver program to test above functions
int main()
{
    int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int* low = (int*)malloc(sizeof(int) * n);
 
    constructLowerArray(arr, low, n);
    printArray(low, n);
    return 0;
}

Java

class CountSmaller {
    void constructLowerArray(int arr[], int countSmaller[],
                             int n)
    {
        int i, j;
 
        // initialize all the counts in countSmaller array
        // as 0
        for (i = 0; i < n; i++)
            countSmaller[i] = 0;
 
        for (i = 0; i < n; i++) {
            for (j = i + 1; j < n; j++) {
                if (arr[j] < arr[i])
                    countSmaller[i]++;
            }
        }
    }
 
    /* Utility function that prints out an array on a line
     */
    void printArray(int arr[], int size)
    {
        int i;
        for (i = 0; i < size; i++)
            System.out.print(arr[i] + " ");
 
        System.out.println("");
    }
 
    // Driver program to test above functions
    public static void main(String[] args)
    {
        CountSmaller small = new CountSmaller();
        int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
        int n = arr.length;
        int low[] = new int[n];
        small.constructLowerArray(arr, low, n);
        small.printArray(low, n);
    }
}

Python3

def constructLowerArray(arr, countSmaller, n):
 
    # initialize all the counts in countSmaller array as 0
    for i in range(n):
        countSmaller[i] = 0
 
    for i in range(n):
        for j in range(i + 1, n):
            if (arr[j] < arr[i]):
                countSmaller[i] += 1
 
# Utility function that prints out an array on a line
 
 
def printArray(arr, size):
    for i in range(size):
        print(arr[i], end=" ")
    print()
 
 
# Driver code
arr = [12, 1, 2, 3, 0, 11, 4]
n = len(arr)
low = [0]*n
constructLowerArray(arr, low, n)
printArray(low, n)
 
# This code is contributed by ApurvaRaj

C#

using System;
 
class GFG {
 
    static void constructLowerArray(int[] arr,
                                    int[] countSmaller,
                                    int n)
    {
        int i, j;
 
        // initialize all the counts in
        // countSmaller array as 0
        for (i = 0; i < n; i++)
            countSmaller[i] = 0;
 
        for (i = 0; i < n; i++) {
            for (j = i + 1; j < n; j++) {
                if (arr[j] < arr[i])
                    countSmaller[i]++;
            }
        }
    }
 
    /* Utility function that prints out
    an array on a line */
    static void printArray(int[] arr, int size)
    {
        int i;
        for (i = 0; i < size; i++)
            Console.Write(arr[i] + " ");
 
        Console.WriteLine("");
    }
 
    // Driver function
    public static void Main()
    {
        int[] arr = new int[] { 12, 1, 2, 3, 0, 11, 4 };
        int n = arr.Length;
        int[] low = new int[n];
 
        constructLowerArray(arr, low, n);
        printArray(low, n);
    }
}
 
// This code is contributed by Sam007

Javascript

function constructLowerArray(arr, countSmaller, n)
{
    let i, j;
 
    // initialize all the counts in
    // countSmaller array as 0
    for (i = 0; i < n; i++)
        countSmaller[i] = 0;
 
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[i])
                countSmaller[i]++;
        }
    }
}
  
/* Utility function that prints out
an array on a line */
function printArray(arr, size)
{
    let i;
    for (i = 0; i < size; i++)
        console.log(arr[i] + " ");
}
   
let arr = [12, 1, 2, 3, 0, 11, 4];
let n = arr.length;
let low = new Array(n);
 
constructLowerArray(arr, low, n);
printArray(low, n);
    

Output

6 1 1 1 0 1 0

Time Complexity: O(N²), Used nested loop for calculating every element in the array of size N.
Auxiliary Space: O(N)

Count smaller elements on the right side using Merge Sort:

The idea is to divide the array into two halves just as we do in merge sort. And then while merging back we sort them in decreasing order and keep track of count the smaller elements.

Follow the steps below to solve the problem:

Declare an array of pair of int V and an array ans to keep track of count. Traverse the given array and insert all the elements and their corresponding index as a pair in this new array. We will call our merge sort function on this array.
In the merge function, we declare two pointers i and j as usual to traverse our left and right array and merge them in descending order.
Now, as we traverse these two arrays, We know that all the elements that are present in right array are also on the right side (in the actual array) of the elements that are present in left array.
So, whenever we find a element in left array which is greater than the element in the right array( V[i].first > V[j].first ) we increase our count ans[ V[i].second ] += size of right array – j +1. Because our arrays are in decreasing order that means all the elements next to it are also smaller than V[i].first.
After increasing the count we just simply do our sorting in decreasing and move our pointers ahead.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
void merge(vector<pair<int, int> >& v, vector<int>& ans,
           int l, int mid, int h)
{
 
    vector<pair<int, int> >
        t; // temporary array for merging both halves
    int i = l;
    int j = mid + 1;
 
    while (i < mid + 1 && j <= h) {
 
        // v[i].first is greater than all
        // the elements from j till h.
        if (v[i].first > v[j].first) {
            ans[v[i].second] += (h - j + 1);
            t.push_back(v[i]);
            i++;
        }
        else {
            t.push_back(v[j]);
            j++;
        }
    }
 
    // if any elements left in left array
    while (i <= mid)
        t.push_back(v[i++]);
    // if any elements left in right array
    while (j <= h)
        t.push_back(v[j++]);
    // putting elements back in main array in
    // descending order
    for (int k = 0, i = l; i <= h; i++, k++)
        v[i] = t[k];
}
 
void mergesort(vector<pair<int, int> >& v, vector<int>& ans,
               int i, int j)
{
    if (i < j) {
        int mid = (i + j) / 2;
 
        // calling mergesort for left half
        mergesort(v, ans, i, mid);
 
        // calling mergesort for right half
        mergesort(v, ans, mid + 1, j);
 
        // merging both halves and generating answer
        merge(v, ans, i, mid, j);
    }
}
 
vector<int> constructLowerArray(int* arr, int n)
{
 
    vector<pair<int, int> > v;
    // inserting elements and corresponding index
    // as pair
    for (int i = 0; i < n; i++)
        v.push_back({ arr[i], i });
 
    // answer array for keeping count
    // initialized by 0,
    vector<int> ans(n, 0);
 
    // calling mergesort
    mergesort(v, ans, 0, n - 1);
 
    return ans;
}
 
// Driver Code Starts.
 
int main()
{
    int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    auto ans = constructLowerArray(arr, n);
    for (auto x : ans) {
        cout << x << " ";
    }
    cout << "\n";
    return 0;
}
// Driver code ends.
 
// This code is contributed by Manjeet Singh

Java

import java.util.*;
 
class LowerArray {
     
    static void merge(int[][] v, int[] ans, int l, int mid, int h)
    {
 
        int[][] t = new int[h - l + 1][2]; // temporary array for merging both halves
        int i = l;
        int j = mid + 1;
        int k = 0;
 
        while (i < mid + 1 && j <= h) {
 
            // v[i][0] is greater than all
            // the elements from j till h.
            if (v[i][0] > v[j][0]) {
                ans[v[i][1]] += (h - j + 1);
                t[k][0] = v[i][0];
                t[k][1] = v[i][1];
                i++;
            }
            else {
                t[k][0] = v[j][0];
                t[k][1] = v[j][1];
                j++;
            }
            k++;
        }
 
        // if any elements left in left array
        while (i <= mid) {
            t[k][0] = v[i][0];
            t[k][1] = v[i][1];
            k++;
            i++;
        }
        // if any elements left in right array
        while (j <= h) {
            t[k][0] = v[j][0];
            t[k][1] = v[j][1];
            k++;
            j++;
        }
        // putting elements back in main array in
        // descending order
        k = 0;
        for (i = l; i <= h; i++, k++) {
            v[i][0] = t[k][0];
            v[i][1] = t[k][1];
        }
    }
 
    static void mergesort(int[][] v, int[] ans, int i, int j)
    {
        if (i < j) {
            int mid = (i + j) / 2;
 
            // calling mergesort for left half
            mergesort(v, ans, i, mid);
 
            // calling mergesort for right half
            mergesort(v, ans, mid + 1, j);
 
            // merging both halves and generating answer
            merge(v, ans, i, mid, j);
        }
    }
 
    static int[] constructLowerArray(int[] arr, int n)
    {
 
        int[][] v = new int[n][2];
        // inserting elements and corresponding index
        // as pair
        for (int i = 0; i < n; i++) {
            v[i][0] = arr[i];
            v[i][1] = i;
        }
 
        // answer array for keeping count
        // initialized by 0,
        int[] ans = new int[n];
 
        // calling mergesort
        mergesort(v, ans, 0, n - 1);
 
        return ans;
    }
 
    // Driver Code Starts.
 
    public static void main(String[] args)
    {
        int[] arr = { 12, 1, 2, 3, 0, 11, 4 };
        int n = arr.length;
 
        int[] ans = constructLowerArray(arr, n);
        for (int x : ans) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

Python3

def merge(v, ans, l, mid, h):
    t = []  # temporary array for merging both halves
    i = l
    j = mid+1
    while (i < mid+1 and j <= h):
       
        # v[i][0] is greater than all
        # the elements from j till h.
        if v[i][0] > v[j][0]:
            ans[v[i][1]] += (h-j+1)
            t.append(v[i])
            i += 1
        else:
            t.append(v[j])
            j += 1
             
    # if any elements left in left array
    while (i <= mid):
        t.append(v[i])
        i += 1
         
    # if any elements left in right array
    while j <= h:
        t.append(v[j])
        j += 1
         
    # putting elements back in main array in
    # descending order
    k = 0
    i = l
    while (i <= h):
        v[i] = t[k]
        i += 1
        k += 1
 
def mergesort(v, ans, i, j):
    if i < j:
        mid = (i+j)//2
         
        # calling mergesort for left half
        mergesort(v, ans, i, mid)
         
        # calling mergesort for right half
        mergesort(v, ans, mid + 1, j)
         
        # merging both halves and generating answer
        merge(v, ans, i, mid, j)
 
 
def constructLowerArray(arr, n):
    v = []
     
    # inserting elements and corresponding index as pair
    for i in range(n):
        v.append([arr[i], i])
         
    # answer array for keeping count initialized by 0
    ans = [0]*n
     
    # calling mergesort
    mergesort(v, ans, 0, n-1)
    return ans
 
# Driver Code
arr = [12, 1, 2, 3, 0, 11, 4]
n = len(arr)
ans = constructLowerArray(arr, n)
for x in ans:
    print(x, end=" ")
     
'''This code is contributed by RAJATKUMARGLA19'''

C#

using System;
using System.Collections.Generic;
 
class Program
{
  static void Merge(List<Tuple<int, int>> v, int[] ans, int l, int mid, int h)
  {
    List<Tuple<int, int>> t = new List<Tuple<int, int>>();// temporary array for merging both halves
    int i = l;
    int j = mid + 1;
 
    while (i < mid + 1 && j <= h)
    {       // v[i].first is greater than all
      // the elements from j till h.
      if (v[i].Item1 > v[j].Item1)
      {
        ans[v[i].Item2] += (h - j + 1);
        t.Add(v[i]);
        i++;
      }
      else
      {
        t.Add(v[j]);
        j++;
      }
    }
 
    // if any elements left in left array
    while (i <= mid)
      t.Add(v[i++]);
 
    // if any elements left in right array
    while (j <= h)
      t.Add(v[j++]);
    i =l;
 
    // putting elements back in main array in
    // descending order
    for (int k = 0; i <= h; i++, k++)
      v[i] = t[k];
  }
 
  static void MergeSort(List<Tuple<int, int>> v, int[] ans, int i, int j)
  {
    if (i < j)
    {
      int mid = (i + j) / 2;
 
      // calling mergesort for left half
      MergeSort(v, ans, i, mid);
 
      // calling mergesort for right half
      MergeSort(v, ans, mid + 1, j);
 
      // merging both halves and generating answer
      Merge(v, ans, i, mid, j);
    }
  }
 
  static int[] ConstructLowerArray(int[] arr)
  {
    List<Tuple<int, int>> v = new List<Tuple<int, int>>();
 
    // inserting elements and corresponding index
    // as pair
    for (int i = 0; i < arr.Length; i++)
      v.Add(new Tuple<int, int>(arr[i], i));
 
    // answer array for keeping count
    // initialized by 0,
    int[] ans = new int[arr.Length];
 
    // calling mergesort
    MergeSort(v, ans, 0, arr.Length - 1);
 
    return ans;
  }
 
  // Driver code
  static void Main(string[] args)
  {
    int[] arr = { 12, 1, 2, 3, 0, 11, 4 };
    int[] ans = ConstructLowerArray(arr);
 
    foreach (int x in ans)
    {
      Console.Write(x + " ");
    }
    Console.WriteLine();
  }
}
 
// This code is contributed by ratiagrawal.

Javascript

function merge( v,ans, l, mid, h)
{
 
    let t=[]; // temporary array for merging both halves
    let i = l;
    let j = mid + 1;
 
    while (i < mid + 1 && j <= h) {
 
        // v[i].first is greater than all
        // the elements from j till h.
        if (j < v.length && v[i][0] > v[j][0]) {
            ans[v[i][1]] += (h - j + 1);
            t.push(v[i]);
            i++;
        }
        else {
            t.push(v[j]);
            j++;
        }
    }
 
    // if any elements left in left array
    while (i <= mid)
    {
        t.push(v[i]);
        i++;
    }
     
    // if any elements left in right array
    while (j <= h)
    {
        t.push(v[j]);
        j++;
    }
     
    // putting elements back in main array in
    // descending order
    for (let k = 0, i = l; i <= h; i++, k++)
        v[i] = t[k];
}
 
function mergesort( v, ans, i, j)
{
    if (i < j) {
        let mid = Math.round((i + j) / 2)-1;
 
        // calling mergesort for left half
        mergesort(v, ans, i, mid);
 
        // calling mergesort for right half
        mergesort(v, ans, mid + 1, j);
 
        // merging both halves and generating answer
        merge(v, ans, i, mid, j);
    }
}
 
function constructLowerArray(arr, n)
{
 
    let v = [];
     
    // inserting elements and corresponding index
    // as pair
    for (let i = 0; i < n; i++)
    {
        let x = [arr[i], i];
        v.push(x);
    }
     
    // answer array for keeping count
    // initialized by 0,
   let ans = new Array(n);
   for(let i = 0; i < n; i++)
   ans[i] = 0;
 
    // calling mergesort
    mergesort(v, ans, 0, n - 1);
 
    return ans;
}
 
// Driver Code Starts.
    let arr= [ 12, 1, 2, 3, 0, 11, 4 ];
    let n = arr.length;
 
    let ans = constructLowerArray(arr, n);
    console.log(ans);
    
   // This code is contributed by garg28harsh.

Output

6 1 1 1 0 1 0

Time Complexity: O(N * log N), Used for Merge Sort.
Auxiliary Space: O(N), Space used to store the pair values in a different array.

Count smaller elements on the right side using Self-Balancing BST:

The idea is to use a Self Balancing Binary Search Tree (AVL, Red Black,.. etc) can be used to get the solution in O(N log N) time complexity. We can augment these trees so that every node N contains the size of the subtree rooted with N.

Follow the steps below to solve the problem:

We traverse the array from right to left and insert all elements in an AVL tree.
While inserting a new key in an AVL tree, first compare the key with the root. If the key is greater than the root, then it is greater than all the nodes in the left subtree of the root.
So we add the size of the left subtree to the count of smaller elements for the key being inserted.
We recursively follow the same approach for all nodes down the root.

Below is the implementation of the above approach.

C++

#include <iostream>
using namespace std;
 
#include <stdio.h>
#include <stdlib.h>
 
// An AVL tree node
struct node {
    int key;
    struct node* left;
    struct node* right;
    int height;
 
    // size of the tree rooted
    // with this node
    int size;
};
 
// A utility function to get
// maximum of two integers
int max(int a, int b);
 
// A utility function to get
// height of the tree rooted with N
int height(struct node* N)
{
    if (N == NULL)
        return 0;
 
    return N->height;
}
 
// A utility function to size
// of the tree of rooted with N
int size(struct node* N)
{
    if (N == NULL)
        return 0;
 
    return N->size;
}
 
// A utility function to
// get maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
 
// Helper function that allocates a
// new node with the given key and
// NULL left and right pointers.
struct node* newNode(int key)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
 
    // New node is initially added at leaf
    node->height = 1;
    node->size = 1;
    return (node);
}
 
// A utility function to right rotate
// subtree rooted with y
struct node* rightRotate(struct node* y)
{
    struct node* x = y->left;
    struct node* T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    // Update sizes
    y->size = size(y->left) + size(y->right) + 1;
    x->size = size(x->left) + size(x->right) + 1;
 
    // Return new root
    return x;
}
 
// A utility function to left rotate
// subtree rooted with x
struct node* leftRotate(struct node* x)
{
    struct node* y = x->right;
    struct node* T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    //  Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
 
    // Update sizes
    x->size = size(x->left) + size(x->right) + 1;
    y->size = size(y->left) + size(y->right) + 1;
 
    // Return new root
    return y;
}
 
// Get Balance factor of node N
int getBalance(struct node* N)
{
    if (N == NULL)
        return 0;
 
    return height(N->left) - height(N->right);
}
 
// Inserts a new key to the tree rotted with
// node. Also, updates *count to contain count
// of smaller elements for the new key
struct node* insert(struct node* node, int key, int* count)
{
    // 1. Perform the normal BST rotation
    if (node == NULL)
        return (newNode(key));
 
    if (key < node->key)
        node->left = insert(node->left, key, count);
    else {
        node->right = insert(node->right, key, count);
 
        // UPDATE COUNT OF SMALLER ELEMENTS FOR KEY
        *count = *count + size(node->left) + 1;
    }
 
    // 2.Update height and size of this ancestor node
    node->height
        = max(height(node->left), height(node->right)) + 1;
    node->size = size(node->left) + size(node->right) + 1;
 
    // 3. Get the balance factor of this
    // ancestor node to check whether this
    // node became unbalanced
    int balance = getBalance(node);
 
    // If this node becomes unbalanced,
    // then there are 4 cases
 
    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    // Return the (unchanged) node pointer
    return node;
}
 
// The following function updates the
// countSmaller array to contain count of
// smaller elements on right side.
void constructLowerArray(int arr[], int countSmaller[],
                         int n)
{
    int i, j;
    struct node* root = NULL;
 
    // Initialize all the counts in
    // countSmaller array as 0
    for (i = 0; i < n; i++)
        countSmaller[i] = 0;
 
    // Starting from rightmost element,
    // insert all elements one by one in
    // an AVL tree and get the count of
    // smaller elements
    for (i = n - 1; i >= 0; i--) {
        root = insert(root, arr[i], &countSmaller[i]);
    }
}
 
// Utility function that prints out an
// array on a line
void printArray(int arr[], int size)
{
    int i;
    cout << "\n";
 
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int* low = (int*)malloc(sizeof(int) * n);
 
    constructLowerArray(arr, low, n);
 
    printArray(low, n);
 
    return 0;
}
 
// This code is contributed by Hemant Jain

C

#include <stdio.h>
#include <stdlib.h>
 
// An AVL tree node
struct node {
    int key;
    struct node* left;
    struct node* right;
    int height;
    int size; // size of the tree rooted with this node
};
 
// A utility function to get maximum of two integers
int max(int a, int b);
 
// A utility function to get height of the tree rooted with
// N
int height(struct node* N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
// A utility function to size of the tree of rooted with N
int size(struct node* N)
{
    if (N == NULL)
        return 0;
    return N->size;
}
 
// A utility function to get maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
 
/* Helper function that allocates a new node with the given
   key and NULL left and right pointers. */
struct node* newNode(int key)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // new node is initially added at leaf
    node->size = 1;
    return (node);
}
 
// A utility function to right rotate subtree rooted with y
struct node* rightRotate(struct node* y)
{
    struct node* x = y->left;
    struct node* T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    // Update sizes
    y->size = size(y->left) + size(y->right) + 1;
    x->size = size(x->left) + size(x->right) + 1;
 
    // Return new root
    return x;
}
 
// A utility function to left rotate subtree rooted with x
struct node* leftRotate(struct node* x)
{
    struct node* y = x->right;
    struct node* T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    //  Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
 
    // Update sizes
    x->size = size(x->left) + size(x->right) + 1;
    y->size = size(y->left) + size(y->right) + 1;
 
    // Return new root
    return y;
}
 
// Get Balance factor of node N
int getBalance(struct node* N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
// Inserts a new key to the tree rotted with node. Also,
// updates *count to contain count of smaller elements for
// the new key
struct node* insert(struct node* node, int key, int* count)
{
    /* 1.  Perform the normal BST rotation */
    if (node == NULL)
        return (newNode(key));
 
    if (key < node->key)
        node->left = insert(node->left, key, count);
    else {
        node->right = insert(node->right, key, count);
 
        // UPDATE COUNT OF SMALLER ELEMENTS FOR KEY
        *count = *count + size(node->left) + 1;
    }
 
    /* 2. Update height and size of this ancestor node */
    node->height
        = max(height(node->left), height(node->right)) + 1;
    node->size = size(node->left) + size(node->right) + 1;
 
    /* 3. Get the balance factor of this ancestor node to
       check whether this node became unbalanced */
    int balance = getBalance(node);
 
    // If this node becomes unbalanced, then there are 4
    // cases
 
    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    /* return the (unchanged) node pointer */
    return node;
}
 
// The following function updates the countSmaller array to
// contain count of smaller elements on right side.
void constructLowerArray(int arr[], int countSmaller[],
                         int n)
{
    int i, j;
    struct node* root = NULL;
 
    // initialize all the counts in countSmaller array as 0
    for (i = 0; i < n; i++)
        countSmaller[i] = 0;
 
    // Starting from rightmost element, insert all elements
    // one by one in an AVL tree and get the count of
    // smaller elements
    for (i = n - 1; i >= 0; i--) {
        root = insert(root, arr[i], &countSmaller[i]);
    }
}
 
/* Utility function that prints out an array on a line */
void printArray(int arr[], int size)
{
    int i;
    printf("\n");
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
}
 
// Driver program to test above functions
int main()
{
    int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int* low = (int*)malloc(sizeof(int) * n);
 
    constructLowerArray(arr, low, n);
 
    printArray(low, n);
    return 0;
}

Java

import java.util.*;
 
class GFG {
 
    // An AVL tree node
    static class node {
        int key;
        node left;
        node right;
        int height;
 
        // size of the tree rooted
        // with this node
        int size;
    };
    static int[] countSmaller;
    static int count;
 
    // A utility function to get
    // height of the tree rooted with N
    static int height(node N)
    {
        if (N == null)
            return 0;
 
        return N.height;
    }
 
    // A utility function to size
    // of the tree of rooted with N
    static int size(node N)
    {
        if (N == null)
            return 0;
 
        return N.size;
    }
 
    // A utility function to
    // get maximum of two integers
    static int max(int a, int b) { return (a > b) ? a : b; }
 
    // Helper function that allocates a
    // new node with the given key and
    // null left and right pointers.
    static node newNode(int key)
    {
        node node = new node();
        node.key = key;
        node.left = null;
        node.right = null;
 
        // New node is initially added at leaf
        node.height = 1;
        node.size = 1;
        return (node);
    }
 
    // A utility function to right rotate
    // subtree rooted with y
    static node rightRotate(node y)
    {
        node x = y.left;
        node T2 = x.right;
 
        // Perform rotation
        x.right = y;
        y.left = T2;
 
        // Update heights
        y.height
            = Math.max(height(y.left), height(y.right)) + 1;
        x.height
            = Math.max(height(x.left), height(x.right)) + 1;
 
        // Update sizes
        y.size = size(y.left) + size(y.right) + 1;
        x.size = size(x.left) + size(x.right) + 1;
 
        // Return new root
        return x;
    }
 
    // A utility function to left rotate
    // subtree rooted with x
    static node leftRotate(node x)
    {
        node y = x.right;
        node T2 = y.left;
 
        // Perform rotation
        y.left = x;
        x.right = T2;
 
        //  Update heights
        x.height
            = Math.max(height(x.left), height(x.right)) + 1;
        y.height
            = Math.max(height(y.left), height(y.right)) + 1;
 
        // Update sizes
        x.size = size(x.left) + size(x.right) + 1;
        y.size = size(y.left) + size(y.right) + 1;
 
        // Return new root
        return y;
    }
 
    // Get Balance factor of node N
    static int getBalance(node N)
    {
        if (N == null)
            return 0;
 
        return height(N.left) - height(N.right);
    }
 
    // Inserts a new key to the tree rotted with
    // node. Also, updates *count to contain count
    // of smaller elements for the new key
    static node insert(node node, int key, int count)
    {
        // 1. Perform the normal BST rotation
        if (node == null)
            return (newNode(key));
 
        if (key < node.key)
            node.left = insert(node.left, key, count);
        else {
            node.right = insert(node.right, key, count);
 
            // UPDATE COUNT OF SMALLER ELEMENTS FOR KEY
            countSmaller[count]
                = countSmaller[count] + size(node.left) + 1;
        }
 
        // 2.Update height and size of this ancestor node
        node.height = Math.max(height(node.left),
                               height(node.right))
                      + 1;
        node.size = size(node.left) + size(node.right) + 1;
 
        // 3. Get the balance factor of this
        // ancestor node to check whether this
        // node became unbalanced
        int balance = getBalance(node);
 
        // If this node becomes unbalanced,
        // then there are 4 cases
 
        // Left Left Case
        if (balance > 1 && key < node.left.key)
            return rightRotate(node);
 
        // Right Right Case
        if (balance < -1 && key > node.right.key)
            return leftRotate(node);
 
        // Left Right Case
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
 
        // Right Left Case
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
 
        // Return the (unchanged) node pointer
        return node;
    }
 
    // The following function updates the
    // countSmaller array to contain count of
    // smaller elements on right side.
    static void constructLowerArray(int arr[], int n)
    {
        int i, j;
        node root = null;
 
        // Initialize all the counts in
        // countSmaller array as 0
        for (i = 0; i < n; i++)
            countSmaller[i] = 0;
 
        // Starting from rightmost element,
        // insert all elements one by one in
        // an AVL tree and get the count of
        // smaller elements
        for (i = n - 1; i >= 0; i--) {
            root = insert(root, arr[i], i);
        }
    }
 
    // Utility function that prints out an
    // array on a line
    static void printArray(int arr[], int size)
    {
        int i;
        System.out.print("\n");
 
        for (i = 0; i < size; i++)
            System.out.print(arr[i] + " ");
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
        int n = arr.length;
 
        countSmaller = new int[n];
 
        constructLowerArray(arr, n);
 
        printArray(countSmaller, n);
    }
}
 
// This code is contributed by Rajput-Ji

Python3

import math
 
 
class GFG:
    # An AVL tree node
    class node:
        key = 0
        left = None
        right = None
        height = 0
        # size of the tree rooted
        # with this node
        size = 0
    countSmaller = None
    count = 0
    # A utility function to get
    # height of the tree rooted with N
 
    @staticmethod
    def height(N):
        if (N == None):
            return 0
        return N.height
    # A utility function to size
    # of the tree of rooted with N
 
    @staticmethod
    def size(N):
        if (N == None):
            return 0
        return N.size
    # A utility function to
    # get maximum of two integers
 
    @staticmethod
    def max(a,  b):
        return a if (a > b) else b
    # Helper function that allocates a
    # new node with the given key and
    # null left and right pointers.
 
    @staticmethod
    def newNode(key):
        node = GFG.node()
        node.key = key
        node.left = None
        node.right = None
        # New node is initially added at leaf
        node.height = 1
        node.size = 1
        return (node)
    # A utility function to right rotate
    # subtree rooted with y
 
    @staticmethod
    def rightRotate(y):
        x = y.left
        T2 = x.right
        # Perform rotation
        x.right = y
        y.left = T2
        # Update heights
        y.height = max(GFG.height(y.left), GFG.height(y.right)) + 1
        x.height = max(GFG.height(x.left), GFG.height(x.right)) + 1
        # Update sizes
        y.size = GFG.size(y.left) + GFG.size(y.right) + 1
        x.size = GFG.size(x.left) + GFG.size(x.right) + 1
        # Return new root
        return x
    # A utility function to left rotate
    # subtree rooted with x
 
    @staticmethod
    def leftRotate(x):
        y = x.right
        T2 = y.left
        # Perform rotation
        y.left = x
        x.right = T2
        #  Update heights
        x.height = max(GFG.height(x.left), GFG.height(x.right)) + 1
        y.height = max(GFG.height(y.left), GFG.height(y.right)) + 1
        # Update sizes
        x.size = GFG.size(x.left) + GFG.size(x.right) + 1
        y.size = GFG.size(y.left) + GFG.size(y.right) + 1
        # Return new root
        return y
    # Get Balance factor of node N
 
    @staticmethod
    def getBalance(N):
        if (N == None):
            return 0
        return GFG.height(N.left) - GFG.height(N.right)
    # Inserts a new key to the tree rotted with
    # node. Also, updates *count to contain count
    # of smaller elements for the new key
 
    @staticmethod
    def insert(node,  key,  count):
        # 1. Perform the normal BST rotation
        if (node == None):
            return (GFG.newNode(key))
        if (key < node.key):
            node.left = GFG.insert(node.left, key, count)
        else:
            node.right = GFG.insert(node.right, key, count)
            # UPDATE COUNT OF SMALLER ELEMENTS FOR KEY
            GFG.countSmaller[count] = GFG.countSmaller[count] + \
                GFG.size(node.left) + 1
        # 2.Update height and size of this ancestor node
        node.height = max(GFG.height(node.left), GFG.height(node.right)) + 1
        node.size = GFG.size(node.left) + GFG.size(node.right) + 1
        # 3. Get the balance factor of this
        # ancestor node to check whether this
        # node became unbalanced
        balance = GFG.getBalance(node)
        # If this node becomes unbalanced,
        # then there are 4 cases
        # Left Left Case
        if (balance > 1 and key < node.left.key):
            return GFG.rightRotate(node)
        # Right Right Case
        if (balance < -1 and key > node.right.key):
            return GFG.leftRotate(node)
        # Left Right Case
        if (balance > 1 and key > node.left.key):
            node.left = GFG.leftRotate(node.left)
            return GFG.rightRotate(node)
        # Right Left Case
        if (balance < -1 and key < node.right.key):
            node.right = GFG.rightRotate(node.right)
            return GFG.leftRotate(node)
        # Return the (unchanged) node pointer
        return node
    # The following function updates the
    # countSmaller array to contain count of
    # smaller elements on right side.
 
    @staticmethod
    def constructLowerArray(arr,  n):
        i = 0
        j = 0
        root = None
        # Initialize all the counts in
        # countSmaller array as 0
        i = 0
        while (i < n):
            GFG.countSmaller[i] = 0
            i += 1
        # Starting from rightmost element,
        # insert all elements one by one in
        # an AVL tree and get the count of
        # smaller elements
        i = n - 1
        while (i >= 0):
            root = GFG.insert(root, arr[i], i)
            i -= 1
    # Utility function that prints out an
    # array on a line
 
    @staticmethod
    def printArray(arr,  size):
        i = 0
        print("\n", end="")
        i = 0
        while (i < size):
            print(str(arr[i]) + " ", end="")
            i += 1
    # Driver code
 
    @staticmethod
    def main(args):
        arr = [12, 1, 2, 3, 0, 11, 4]
        n = len(arr)
        GFG.countSmaller = [0] * (n)
        GFG.constructLowerArray(arr, n)
        GFG.printArray(GFG.countSmaller, n)
 
 
if __name__ == "__main__":
    GFG.main([])

C#

using System;
public class GFG {
 
    // An AVL tree node
    public class node {
        public int key;
        public node left;
        public node right;
        public int height;
 
        // size of the tree rooted
        // with this node
        public int size;
    };
 
    static int[] countSmaller;
    static int count;
 
    // A utility function to get
    // height of the tree rooted with N
    static int height(node N)
    {
        if (N == null)
            return 0;
 
        return N.height;
    }
 
    // A utility function to size
    // of the tree of rooted with N
    static int size(node N)
    {
        if (N == null)
            return 0;
 
        return N.size;
    }
 
    // A utility function to
    // get maximum of two integers
    static int max(int a, int b) { return (a > b) ? a : b; }
 
    // Helper function that allocates a
    // new node with the given key and
    // null left and right pointers.
    static node newNode(int key)
    {
        node node = new node();
        node.key = key;
        node.left = null;
        node.right = null;
 
        // New node is initially added at leaf
        node.height = 1;
        node.size = 1;
        return (node);
    }
 
    // A utility function to right rotate
    // subtree rooted with y
    static node rightRotate(node y)
    {
        node x = y.left;
        node T2 = x.right;
 
        // Perform rotation
        x.right = y;
        y.left = T2;
 
        // Update heights
        y.height
            = Math.Max(height(y.left), height(y.right)) + 1;
        x.height
            = Math.Max(height(x.left), height(x.right)) + 1;
 
        // Update sizes
        y.size = size(y.left) + size(y.right) + 1;
        x.size = size(x.left) + size(x.right) + 1;
 
        // Return new root
        return x;
    }
 
    // A utility function to left rotate
    // subtree rooted with x
    static node leftRotate(node x)
    {
        node y = x.right;
        node T2 = y.left;
 
        // Perform rotation
        y.left = x;
        x.right = T2;
 
        // Update heights
        x.height
            = Math.Max(height(x.left), height(x.right)) + 1;
        y.height
            = Math.Max(height(y.left), height(y.right)) + 1;
 
        // Update sizes
        x.size = size(x.left) + size(x.right) + 1;
        y.size = size(y.left) + size(y.right) + 1;
 
        // Return new root
        return y;
    }
 
    // Get Balance factor of node N
    static int getBalance(node N)
    {
        if (N == null)
            return 0;
 
        return height(N.left) - height(N.right);
    }
 
    // Inserts a new key to the tree rotted with
    // node. Also, updates *count to contain count
    // of smaller elements for the new key
    static node insert(node node, int key, int count)
    {
        // 1. Perform the normal BST rotation
        if (node == null)
            return (newNode(key));
 
        if (key < node.key)
            node.left = insert(node.left, key, count);
        else {
            node.right = insert(node.right, key, count);
 
            // UPDATE COUNT OF SMALLER ELEMENTS FOR KEY
            countSmaller[count]
                = countSmaller[count] + size(node.left) + 1;
        }
 
        // 2.Update height and size of this ancestor node
        node.height = Math.Max(height(node.left),
                               height(node.right))
                      + 1;
        node.size = size(node.left) + size(node.right) + 1;
 
        // 3. Get the balance factor of this
        // ancestor node to check whether this
        // node became unbalanced
        int balance = getBalance(node);
 
        // If this node becomes unbalanced,
        // then there are 4 cases
 
        // Left Left Case
        if (balance > 1 && key < node.left.key)
            return rightRotate(node);
 
        // Right Right Case
        if (balance < -1 && key > node.right.key)
            return leftRotate(node);
 
        // Left Right Case
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
 
        // Right Left Case
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
 
        // Return the (unchanged) node pointer
        return node;
    }
 
    // The following function updates the
    // countSmaller array to contain count of
    // smaller elements on right side.
    static void constructLowerArray(int[] arr, int n)
    {
        int i, j;
        node root = null;
 
        // Initialize all the counts in
        // countSmaller array as 0
        for (i = 0; i < n; i++)
            countSmaller[i] = 0;
 
        // Starting from rightmost element,
        // insert all elements one by one in
        // an AVL tree and get the count of
        // smaller elements
        for (i = n - 1; i >= 0; i--) {
            root = insert(root, arr[i], i);
        }
    }
 
    // Utility function that prints out an
    // array on a line
    static void printArray(int[] arr, int size)
    {
        int i;
        Console.Write("\n");
 
        for (i = 0; i < size; i++)
            Console.Write(arr[i] + " ");
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] arr = { 12, 1, 2, 3, 0, 11, 4 };
        int n = arr.Length;
 
        countSmaller = new int[n];
 
        constructLowerArray(arr, n);
 
        printArray(countSmaller, n);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

let countSmaller;
let count;
   // An AVL tree node
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    this.height = 1;
    this.size = 1;
  }
}
 
// A utility function to get height of the tree rooted with N
function height(N) {
  if (N === null) return 0;
  return N.height;
}
 
// A utility function to size of the tree of rooted with N
function size(N) {
  if (N === null) return 0;
  return N.size;
}
 
// A utility function to get maximum of two integers
function max(a, b) {
  return a > b ? a : b;
}
 
// Helper function that allocates a new node with the given key and null left and right pointers.
function newNode(key) {
  let node = new Node(key);
  node.key = key;
  node.left = null;
  node.right = null;
 
  // New node is initially added at leaf
  node.height = 1;
  node.size = 1;
  return node;
}
 
// A utility function to right rotate subtree rooted with y
function rightRotate(y) {
  let x = y.left;
  let T2 = x.right;
 
  // Perform rotation
  x.right = y;
  y.left = T2;
 
  // Update heights
  y.height = max(height(y.left), height(y.right)) + 1;
  x.height = max(height(x.left), height(x.right)) + 1;
 
  // Update sizes
  y.size = size(y.left) + size(y.right) + 1;
  x.size = size(x.left) + size(x.right) + 1;
 
  // Return new root
  return x;
}
 
// A utility function to left rotate subtree rooted with x
function leftRotate(x) {
  let y = x.right;
  let T2 = y.left;
 
  // Perform rotation
  y.left = x;
  x.right = T2;
 
  // Update heights
  x.height = max(height(x.left), height(x.right)) + 1;
  y.height = max(height(y.left), height(y.right)) + 1;
 
  // Update sizes
  x.size = size(x.left) + size(x.right) + 1;
  y.size = size(y.left) + size(y.right) + 1;
 
  // Return new root
  return y;
}
 
// Get Balance factor of node N
function getBalance(N) {
  if (N === null) return 0;
  return height(N.left) - height(N.right);
}
 
// Inserts a new key to the tree rotted with node.
// Also, updates *count to contain count of smaller elements for the new key
function insert(node, key, count) {
  // 1. Perform the normal BST rotation
  if (node === null) return newNode(key);
 
  if (key < node.key) node.left = insert(node.left, key, count);
  else {
    node.right = insert(node.right, key, count);
 
    // UPDATE COUNT OF SMALLER ELEMENTS FOR KEY
    countSmaller[count] = countSmaller[count] + size(node.left) + 1;
  }
 
  // 2.Update height and size of this ancestor node
  node.height = max(height(node.left), height(node.right)) + 1;
  node.size = size(node.left) + size(node.right) + 1;
 
  // 3. Get the balance factor of this ancestor node to check
 
// whether this node became unbalanced
let balance = getBalance(node);
 
// If this node becomes unbalanced, then there are 4 cases
 
// Left Left Case
if (balance > 1 && key < node.left.key) {
return rightRotate(node);
}
 
// Right Right Case
if (balance < -1 && key > node.right.key) {
return leftRotate(node);
}
 
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
 
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
 
// Return the (unchanged) node pointer
return node;
}
 
// Function to initialize countSmaller array
function initializeCountSmaller(arr, n) {
    countSmaller = new Array(n);
// Initialize all element counts as 0
for (let i = 0; i < n; i++) {
countSmaller[i] = 0;
}
 
// Construct and insert all elements in AVL
// tree one by one. Doing this updates
// countSmaller[] for each inserted item
let root = null;
for (let i = n - 1; i >= 0; i--) {
root = insert(root, arr[i], i);
}
}
 
// Function to print countSmaller array
function printCountSmaller(arr, n) {
for (let i = 0; i < n; i++) {
document.write(countSmaller[i] + " ");
}
}
 
// Example usage
let arr = [12, 1, 2, 3, 0, 11, 4];
let n = arr.length;
countSmaller = new Array(n);
initializeCountSmaller(arr, n);
printCountSmaller(arr, n);

Output

6 1 1 1 0 1 0

Time Complexity: O(N * log N), Used self-balancing bst which takes logN time for every operation.
Auxiliary Space: O(N), Space used to store the nodes

Count smaller elements on the right side using BST with 2 extra fields:

The idea is to use a simple Binary Search Tree with 2 extra fields:

to hold the elements on the left side of a node

to store the frequency of element.

Follow the steps below to solve the problem:

Traverse the input array from the ending to the beginning and add the elements into the BST.
While inserting the elements into the BST, compute the number of elements that are lesser elements simply by computing the sum of the frequency of the element
And the number of elements to the left side of the current node
if we are moving to the right side of the current node.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// BST node structure
class Node {
 
public:
    int val;
    int count;
    Node* left;
    Node* right;
 
    // Constructor
    Node(int num1, int num2)
    {
        this->val = num1;
        this->count = num2;
        this->left = this->right = NULL;
    }
};
 
// Function to addNode and find the smaller
// elements on the right side
int addNode(Node*& root, int value, int countSmaller)
{
 
    // Base case
    if (root == NULL) {
        root = new Node(value, 0);
        return countSmaller;
    }
    if (root->val < value) {
        return root->count
               + addNode(root->right, value,
                         countSmaller + 1);
    }
    else {
        root->count++;
        return addNode(root->left, value, countSmaller);
    }
}
 
// Driver code
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int data[] = { 12, 1, 2, 3, 0, 11, 4 };
    int size = sizeof(data) / sizeof(data[0]);
    int ans[size] = { 0 };
 
    Node* root = NULL;
 
    for (int i = size - 1; i >= 0; i--) {
        ans[i] = addNode(root, data[i], 0);
    }
 
    for (int i = 0; i < size; i++)
        cout << ans[i] << " ";
 
    return 0;
}
 
// This code is contributed by divyanshu gupta

Python3

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
        # denotes number of times (frequency)
        # an element has occurred.
        self.elecount = 1
 
        # denotes the number of nodes on left
        # side of the node encountered so far.
        self.lcount = 0
 
 
class Tree:
    def __init__(self, root):
        self.root = root
 
    def insert(self, node):
        """This function helps to place an element at 
            its correct position in the BST and returns 
            the count of elements which are smaller than 
            the elements which are already inserted into the BST. 
        """
        curr = self.root
        cnt = 0
        while curr != None:
            prev = curr
            if node.val > curr.val:
 
                # This step computes the number of elements
                # which are less than the current Node.
                cnt += (curr.elecount+curr.lcount)
                curr = curr.right
            elif node.val < curr.val:
                curr.lcount += 1
                curr = curr.left
            else:
                prev = curr
                prev.elecount += 1
                break
        if prev.val > node.val:
            prev.left = node
        elif prev.val < node.val:
            prev.right = node
        else:
            return cnt+prev.lcount
        return cnt
 
 
def constructArray(arr, n):
    t = Tree(Node(arr[-1]))
    ans = [0]
    for i in range(n-2, -1, -1):
        ans.append(t.insert(Node(arr[i])))
    return reversed(ans)
 
# Driver function for above code
 
 
def main():
    n = 7
    arr = [12, 1, 2, 3, 0, 11, 4]
    print(" ".join(list(map(str, constructArray(arr, n)))))
 
 
if __name__ == "__main__":
    main()
 
# Code Contributed by Tarun Gudipati

C#

// C# program to implement above logic
using System;
 
// BST node structure
class GFG {
    class Node {
        public int val;
        public int count;
        public Node left;
        public Node right;
 
        // Constructor
        public Node(int num1, int num2)
        {
            val = num1;
            count = num2;
            left = right = null;
        }
    }
    static Node root = null;
 
    // Function to addNode and find the smaller
    // elements on the right side
    int addNode(ref Node root, int value, int countSmaller)
    {
        // Base case
        if (root == null) {
            root = new Node(value, 0);
            return countSmaller;
        }
        if (root.val < value) {
            return root.count
                + addNode(ref root.right, value,
                          countSmaller + 1);
        }
        else {
            root.count += 1;
            return addNode(ref root.left, value,
                           countSmaller);
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        GFG tree = new GFG();
        int[] data = { 12, 1, 2, 3, 0, 11, 4 };
        int size = data.Length;
        int[] ans = new int[size];
 
        for (int i = size - 1; i >= 0; i--) {
            ans[i] = tree.addNode(ref root, data[i], 0);
        }
        for (int i = 0; i < size; i++)
            Console.Write(ans[i] + " ");
    }
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Java

class Node {
    int val;
    int elecount;
    int lcount;
    Node left, right;
    Node(int val) {
        this.val = val;
        this.elecount = 1;
        this.lcount = 0;
        this.left = null;
        this.right = null;
    }
}
 
class Tree {
    Node root;
    Tree(Node root) {
        this.root = root;
    }
    int insert(Node node) {
        int cnt = 0;
        Node curr = root, prev = null;
        while (curr != null) {
            prev = curr;
            if (node.val > curr.val) {
                cnt += curr.elecount + curr.lcount;
                curr = curr.right;
            } else if (node.val < curr.val) {
                curr.lcount++;
                curr = curr.left;
            } else {
                prev = curr;
                prev.elecount++;
                break;
            }
        }
        if (prev.val > node.val) {
            prev.left = node;
        } else if (prev.val < node.val) {
            prev.right = node;
        } else {
            return cnt + prev.lcount - 1;
        }
        return cnt;
    }
}
 
public class Main {
    public static void main(String[] args) {
        int[] data = { 12, 1, 2, 3, 0, 11, 4 };
        int n = data.length;
        int[] ans = new int[n];
        Tree tree = new Tree(new Node(data[n-1]));
        for (int i = n-2; i >= 0; i--) {
            ans[i] = tree.insert(new Node(data[i]));
        }
        for (int i = 0; i < n; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}

Javascript

// BST node structure
class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.elecount = 1;
        this.lcount = 0;
    }
}
 
class Tree {
    constructor(root) {
        this.root = root;
    }
    // Function to addNode and find the smaller
    // elements on the right side
    insert(node) {
        let curr = this.root;
        let cnt = 0;
        let prev = null;
        while (curr != null) {
            prev = curr;
            if (node.val > curr.val) {
                cnt += (curr.elecount + curr.lcount);
                curr = curr.right;
            } else if (node.val < curr.val) {
                curr.lcount += 1;
                curr = curr.left;
            } else {
                prev = curr;
                prev.elecount += 1;
                break;
            }
        }
        if (prev.val > node.val) {
            prev.left = node;
        } else if (prev.val < node.val) {
            prev.right = node;
        } else {
            return cnt + prev.lcount;
        }
        return cnt;
    }
}
 
function constructArray(arr, n) {
    let t = new Tree(new Node(arr[n - 1]));
    let ans = [0];
    for (let i = n - 2; i >= 0; i--) {
        ans.push(t.insert(new Node(arr[i])));
    }
    return ans.reverse();
}
 
function main() {
    let n = 7;
    let arr = [12, 1, 2, 3, 0, 11, 4];
    console.log(constructArray(arr, n).join(" "));
}
 
main();
 
// This code is contributed by akashish__

Output

6 1 1 1 0 1 0

Time Complexity: O(N²) as adding step can take O(N) time.
Auxiliary Space: O(N), Space used to store the elements.

Count smaller elements on right side using Set in C++ STL
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Here’s a simple and concise approach to solve the above problem.

Follow the steps below to solve the problem:

We start iterating from the end of the array to the beginning.
For each element, we find the index where it can be inserted in a sorted array of all the elements to its right. This is done using the lower_bound function.
The number of elements to the right of the current element that are smaller than it is the same as the index where it can be inserted in the sorted array.
We insert the current element in the sorted array at the appropriate index using the insert function.
We store the number of smaller elements for the current element in a separate list.
Finally, we return the list of counts, which is the desired output.

Below is the implementation of above approach

C++

#include <bits/stdc++.h>
using namespace std;
 
class Solution {
public:
    vector<int> constructLowerArray(vector<int>& arr) {
        vector<int> ans, temp;
        int n = arr.size();
        for (int i = n - 1; i >= 0; i--) {
            int c = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin();
            ans.push_back(c);
            temp.insert(temp.begin() + c, arr[i]);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
 
int main() {
    vector<int> arr = {12, 1, 2, 3, 0, 11, 4};
    Solution obj;
    vector<int> ans = obj.constructLowerArray(arr);
    for (int x : ans) cout << x << " ";  // Output: 6 1 1 1 0 1 0
    return 0;
}

Java

import java.util.*;
 
class Solution {
    public List<Integer> constructLowerArray(int[] arr) {
        List<Integer> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        int n = arr.length;
        for (int i = n - 1; i >= 0; i--) {
            int c = Collections.binarySearch(temp, arr[i]);
            if (c < 0) c = -c - 1;
            ans.add(c);
            temp.add(c, arr[i]);
        }
        Collections.reverse(ans);
        return ans;
    }
}
 
class Main {
    public static void main(String[] args) {
        int[] arr = {12, 1, 2, 3, 0, 11, 4};
        Solution obj = new Solution();
        List<Integer> ans = obj.constructLowerArray(arr);
        for (int x : ans) System.out.print(x + " ");  // Output: 6 1 1 1 0 1 0
    }
}

Python3

import bisect
 
class Solution:
    def constructLowerArray(self, arr, n):
        ans = []
        temp = []
         
        for i in range(n - 1, -1, -1):
            c = bisect.bisect_left(temp, arr[i])
            ans.append(c)
            temp = [arr[i]]
         
        return ans[::-1]
 
arr = [12, 1, 2, 3, 0, 11, 4]
n = len(arr)
 
s = Solution()
ans = s.constructLowerArray(arr, n)
 
print(*ans)

C#

using System;
 
class Solution {
    public int[] ConstructLowerArray(int[] arr, int n) {
        int[] ans = new int[n];
        int[] temp = new int[n];
         
        for (int i = n - 1; i >= 0; i--) {
            int c = Array.BinarySearch(temp, 0, n - i - 1, arr[i]);
            if (c < 0) {
                c = ~c;
            }
            ans[i] = c;
            Array.Copy(temp, c, temp, c + 1, n - i - c - 1);
            temp = arr[i];
        }
         
        return ans;
    }
}
 
class Program {
    static void Main(string[] args) {
        int[] arr = {12, 1, 2, 3, 0, 11, 4};
        int n = arr.Length;
         
        Solution s = new Solution();
        int[] ans = s.ConstructLowerArray(arr, n);
         
        Console.Write(string.Join(" ", ans));
    }
}

Javascript

class Solution {
  constructLowerArray(arr, n) {
    let ans = [], temp = [];
    for (let i = n - 1; i >= 0; i--) {
      let c = temp.findIndex((val) => val >= arr[i]);
      ans.push(c === -1 ? temp.length : c);
      temp.splice(c === -1 ? temp.length : c, 0, arr[i]);
    }
    return ans.reverse();
  }
}
 
let obj = new Solution();
let arr = [12, 1, 2, 3, 0, 11, 4];
let n = arr.length;
let ans = obj.constructLowerArray(arr, n);
console.log(ans);  // Output: [6, 1, 1, 1, 0, 1, 0]

Output

6 1 1 1 0 1 0

The time complexity of the constructLowerArray method in the Solution class is O(n log n)
The space complexity is also O(n) because of the use of two lists ans and temp with n elements.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Count smaller elements on Right side

C++

C

Java

Python3

C#

Javascript

Count smaller elements on the right side using Merge Sort:

C++

Java

Python3

C#

Javascript

Count smaller elements on the right side using Self-Balancing BST:

C++

C

Java

Python3

C#

Javascript

Count smaller elements on the right side using BST with 2 extra fields:

C++

Python3

C#

Java

Javascript

Here’s a simple and concise approach to solve the above problem.

Follow the steps below to solve the problem:

C++

Java

Python3

C#

Javascript

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US