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:
http://ideone.com/QtAjCa
static class Node{
int data;
Node left;
Node right;
int count;
int smallerCount;
public Node(int data){
this.data = data;
}
}
public static void main(String[] args){
int[] arr = new int[]{12, 1, 2, 3, 0, 11, 4};
System.out.println("Input array");
for(int i: arr)
System.out.print(i+",");
Node dummyNode = new Node(-Integer.MAX_VALUE);
int[] countSmaller = new int[arr.length];
for(int i=arr.length-1;i>=0;i--){
Node node = new Node(arr[i]);
push(node,dummyNode);
countSmaller[i] = node.smallerCount;
}
System.out.println("\nOutput array");
for(int i: countSmaller)
System.out.print(i+",");
System.out.println("");
}
private static void push(Node node, Node head){
if(head != null){
if(head.data < node.data){
head.count++;
//System.out.println("head.data="+head.data);
node.smallerCount += (head.left == null)?1:(head.left.count+2);
if(head.right == null){
node.smallerCount--; //to account for dummy node;
//System.out.println(node.data+" - number of smaller elements on right >>"+node.smallerCount);
head.right = node;
} else{
push(node, head.right);
}
} else if(head.data > node.data){
head.count++;
if(head.left == null){
head.left = node;
node.smallerCount--; //to account for dummy node;
//System.out.println(node.data+" - number of smaller elements on right >>"+node.smallerCount);
} else{
push(node,head.left);
}
}
}
}
Read full article from Count smaller elements on right side | GeeksforGeeks
Examples:
Input: arr[] = {12, 1, 2, 3, 0, 11, 4}
Output: countSmaller[] = {6, 1, 1, 1, 0, 1, 0}
Method 2 (Use Self Balancing BST)
A Self Balancing Binary Search Tree (AVL, Red Black,.. etc) can be used to get the solution in O(nLogn) time complexity. We can augment these trees so that every node N contains size the subtree rooted with N. We have used AVL tree in the following implementation.
A Self Balancing Binary Search Tree (AVL, Red Black,.. etc) can be used to get the solution in O(nLogn) time complexity. We can augment these trees so that every node N contains size the subtree rooted with N. We have used AVL tree in the following implementation.
We traverse the array from right to left and insert all elements one by one in an AVL tree. While inserting a new key in an AVL tree, we first compare the key with root. If key is greater than root, then it is greater than all the nodes in left subtree of root. So we add the size of left subtree to the count of smaller element for the key being inserted. We recursively follow the same approach for all nodes down the root.
// 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]);
}
}
static class Node{
int data;
Node left;
Node right;
int count;
int smallerCount;
public Node(int data){
this.data = data;
}
}
public static void main(String[] args){
int[] arr = new int[]{12, 1, 2, 3, 0, 11, 4};
System.out.println("Input array");
for(int i: arr)
System.out.print(i+",");
Node dummyNode = new Node(-Integer.MAX_VALUE);
int[] countSmaller = new int[arr.length];
for(int i=arr.length-1;i>=0;i--){
Node node = new Node(arr[i]);
push(node,dummyNode);
countSmaller[i] = node.smallerCount;
}
System.out.println("\nOutput array");
for(int i: countSmaller)
System.out.print(i+",");
System.out.println("");
}
private static void push(Node node, Node head){
if(head != null){
if(head.data < node.data){
head.count++;
//System.out.println("head.data="+head.data);
node.smallerCount += (head.left == null)?1:(head.left.count+2);
if(head.right == null){
node.smallerCount--; //to account for dummy node;
//System.out.println(node.data+" - number of smaller elements on right >>"+node.smallerCount);
head.right = node;
} else{
push(node, head.right);
}
} else if(head.data > node.data){
head.count++;
if(head.left == null){
head.left = node;
node.smallerCount--; //to account for dummy node;
//System.out.println(node.data+" - number of smaller elements on right >>"+node.smallerCount);
} else{
push(node,head.left);
}
}
}
}
Read full article from Count smaller elements on right side | GeeksforGeeks