Algorithms
Count smaller elements on the right
Given an array of Integer. Find number of smaller elements at each position. Array may have duplicate elements.
The brute force solution for this problem would be to traverse the array from right to left and count number of smaller element on the right in O(n^2).
Faster Implementation
I have described in a previous post how to compute smaller elements count on right by using Divide and Conquer technique in O(nlgn) time. It is similar to counting inversions in an array.
Alternative Method using AVL tree
But we can do it more efficiently using balanced BST such as AVL tree. Observe that, If a key is greater than root, then it is greater than all the nodes in left subtree of root.
So, We will consider each number in an array as a BST node and insert them in a AVL tree one by one from right to left. During each insert we will keep updating the size of left subtree at the node being inserted. This will give us our desired smaller element count. We also need to handle balancing the tree while insert.
A balance tree got imbalanced on an insert when the insert on a subtree rooted at a node x makes difference between left subtree and right subtree height more than 1. We will have to consider 4 cases:
1) Insert-in-left-of-left-subtree of x: we can balance by rotating x right
2) Insert-in-right-of-right-subtree of x: we can balance by rotating x left
3) Insert-in-right-of-left-subtree of x: we need two rotations: balance left of x by rotating left. And then a right rotation of x.
4) Insert-in-left-of-right-subtree of x: we need two rotations: balance right of x by rotating right. And then a left rotation of x.
Time complexity will be O(nlgn) and space is O(n).
protected class TreeNode {
int key;
int height;
int size;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(final int key) {
this.key = key;
this.size = 1;
this.height = 1;
this.left = null;
this.right = null;
}
}
public int size(final TreeNode node) {
return node == null ? 0 : node.size;
}
public int height(final TreeNode node) {
return node == null ? 0 : node.height;
}
public TreeNode rotateLeft(final TreeNode root) {
final TreeNode newRoot = root.right;
final TreeNode leftSubTree = newRoot.left;
newRoot.left = root;
root.right = leftSubTree;
root.height = max(height(root.left), height(root.right)) + 1;
newRoot.height = max(height(newRoot.left), height(newRoot.right)) + 1;
newRoot.size = size(newRoot.left) + size(newRoot.right) + 1;
newRoot.size = size(newRoot.left) + size(newRoot.right) + 1;
return newRoot;
}
public TreeNode rotateRight(final TreeNode root) {
final TreeNode newRoot = root.left;
final TreeNode rightSubTree = newRoot.right;
newRoot.right = root;
root.left = rightSubTree;
root.height = max(height(root.left), height(root.right)) + 1;
newRoot.height = max(height(newRoot.left), height(newRoot.right)) + 1;
newRoot.size = size(newRoot.left) + size(newRoot.right) + 1;
newRoot.size = size(newRoot.left) + size(newRoot.right) + 1;
return newRoot;
}
public int max(final int a, final int b) {
return a >= b ? a : b;
}
public TreeNode insertIntoAVL(final TreeNode node, final int key, final int count[], final int index) {
if (node == null) {
return new TreeNode(key);
}
if (node.key > key) {
node.left = insertIntoAVL(node.left, key, count, index);
} else {
node.right = insertIntoAVL(node.right, key, count, index);
// update smaller elements count
count[index] = count[index] + size(node.left) + 1;
}
// update the size and height
node.height = max(height(node.left), height(node.right)) + 1;
node.size = size(node.left) + size(node.right) + 1;
// balance the tree
final int balance = height(node.left) - height(node.right);
// left-left
if (balance > 1 && node.key > key) {
return rotateRight(node);
}
// right-right
if (balance < -1 && node.key > key) {
return rotateLeft(node);
}
// left-right
if (balance > 1 && node.key < key) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
// right-left
if (balance > 1 && node.key < key) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
public int[] countSmallerOnRight(final int[] in) {
final int[] smaller = new int[in.length];
TreeNode root = null;
for (int i = in.length - 1; i >= 0; i--) {
root = insertIntoAVL(root, in[i], smaller, i);
}
return smaller;
}