class SmallOnRight{
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)
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)
}
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);
}
}
}
}
}
Y2xhc3MgU21hbGxPblJpZ2h0ewoJc3RhdGljIGNsYXNzIE5vZGV7CgkJaW50IGRhdGE7CgkJTm9kZSBsZWZ0OwoJCU5vZGUgcmlnaHQ7CgkJaW50IGNvdW50OwoJCWludCBzbWFsbGVyQ291bnQ7CgkJcHVibGljIE5vZGUoaW50IGRhdGEpewoJCQl0aGlzLmRhdGEgPSBkYXRhOwoJCX0KCX0KCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKXsKCQlpbnRbXSBhcnIgPSBuZXcgaW50W117MTIsIDEsIDIsIDMsIDAsIDExLCA0fTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIklucHV0IGFycmF5Iik7CgkJZm9yKGludCBpOiBhcnIpCgkJCVN5c3RlbS5vdXQucHJpbnQoaSsiLCIpOwoKCQlOb2RlIGR1bW15Tm9kZSA9IG5ldyBOb2RlKC1JbnRlZ2VyLk1BWF9WQUxVRSk7CgkJaW50W10gY291bnRTbWFsbGVyID0gbmV3IGludFthcnIubGVuZ3RoXTsKCQlmb3IoaW50IGk9YXJyLmxlbmd0aC0xO2k+PTA7aS0tKXsKCQkJTm9kZSBub2RlID0gbmV3IE5vZGUoYXJyW2ldKTsKCQkJcHVzaChub2RlLGR1bW15Tm9kZSk7CgkJCWNvdW50U21hbGxlcltpXSA9IG5vZGUuc21hbGxlckNvdW50OwoJCX0KCQkKCQlTeXN0ZW0ub3V0LnByaW50bG4oIlxuT3V0cHV0IGFycmF5Iik7CgkJZm9yKGludCBpOiBjb3VudFNtYWxsZXIpCgkJCVN5c3RlbS5vdXQucHJpbnQoaSsiLCIpOwoJCVN5c3RlbS5vdXQucHJpbnRsbigiIik7Cgl9CgoJcHJpdmF0ZSBzdGF0aWMgdm9pZCBwdXNoKE5vZGUgbm9kZSwgTm9kZSBoZWFkKXsKCQlpZihoZWFkICE9IG51bGwpewoJCQlpZihoZWFkLmRhdGEgPCBub2RlLmRhdGEpewoJCQkJaGVhZC5jb3VudCsrOwoJCQkJLy9TeXN0ZW0ub3V0LnByaW50bG4oImhlYWQuZGF0YT0iK2hlYWQuZGF0YSk7CgkJCQlub2RlLnNtYWxsZXJDb3VudCArPSAoaGVhZC5sZWZ0ID09IG51bGwpPzE6KGhlYWQubGVmdC5jb3VudCsyKTsKCQkJCWlmKGhlYWQucmlnaHQgPT0gbnVsbCl7CgkJCQkJbm9kZS5zbWFsbGVyQ291bnQtLTsJLy90byBhY2NvdW50IGZvciBkdW1teSBub2RlOwoJCQkJCS8vU3lzdGVtLm91dC5wcmludGxuKG5vZGUuZGF0YSsiIC0gbnVtYmVyIG9mIHNtYWxsZXIgZWxlbWVudHMgb24gcmlnaHQgPj4iK25vZGUuc21hbGxlckNvdW50KTsKCQkJCQloZWFkLnJpZ2h0ID0gbm9kZTsKCQkJCX0gZWxzZXsKCQkJCQlwdXNoKG5vZGUsIGhlYWQucmlnaHQpOwoJCQkJfQoJCQl9IGVsc2UgaWYoaGVhZC5kYXRhID4gbm9kZS5kYXRhKXsKCQkJCWhlYWQuY291bnQrKzsKCQkJCWlmKGhlYWQubGVmdCA9PSBudWxsKXsKCQkJCQloZWFkLmxlZnQgPSBub2RlOwoJCQkJCW5vZGUuc21hbGxlckNvdW50LS07CS8vdG8gYWNjb3VudCBmb3IgZHVtbXkgbm9kZTsKCQkJCQkvL1N5c3RlbS5vdXQucHJpbnRsbihub2RlLmRhdGErIiAtIG51bWJlciBvZiBzbWFsbGVyIGVsZW1lbnRzIG9uIHJpZ2h0ID4+Iitub2RlLnNtYWxsZXJDb3VudCk7CgkJCQl9IGVsc2V7CgkJCQkJcHVzaChub2RlLGhlYWQubGVmdCk7CgkJCQl9CgkJCX0KCQl9Cgl9Cn0=
Input array
12,1,2,3,0,11,4,
Output array
6,1,1,1,0,1,0,