Count smaller elements on right side

Source

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

Examples:

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

(Corner Cases)
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}

Method 1 (Simple)
Use two 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[].

void constructLowerArray (int *arr[], int *low, 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, 10, 5, 4, 2, 20, 6, 1, 0, 2};   int n = sizeof(arr)/sizeof(arr[0]);   int *low = (int *)malloc(sizeof(int)*n);   constructLowerArray(arr, low, n);   printArray(low, n);   return 0; }

Time Complexity: O(n^2)
Auxiliary Space: O(1)

Method 2 (Use BST)
A Self Balancing Binary Search Tree (AVL, Red Black,.. etc) can be used to get the solution in O(nLogn) time complexity. A Self Balancing Binary Search Tree(BST) can be augmented to contain count of smaller values in every node. We can store this info by storing count of nodes in left subtree. The BST insert function must be augmented in such a way that it increments the count for those ancestors for which, the node being inserted is in left subtree. The BST delete function must also be augmented in such a way that decrements the count for those ancestors for which, the node being deleted is in left subtree. Both of these operations can still be done in O(Logn) complexity.

Following is the algorithm that constructs countSmaller[] using the above Augmented Self Balancing BST.

1) Traverse the array from left to right and construct a BST such that every node of BST also contains count of nodes in left subtree. O(nLogn)
2) Traverse the array again from left to right and do following for every array element arr[i] .
…..a) Search the element arr[i] in BST, get the count of nodes in left subtree and store it in countSmaller[i]
…..b) Delete the node (which contains arr[i]) from BST

The step 2 b) is necessary to make sure that the smaller nodes on left side (in array) are deleted before we consider count for a node.

Time Complexity: O(nLogn)
Auxiliary Space: O(n)