fork download
copy 
  1. class SmallOnRight{
  2. 	static class Node{
  3. 		int data;
  4. 		Node left;
  5. 		Node right;
  6. 		int count;
  7. 		int smallerCount;
  8. 		public Node(int data){
  9. 			this.data = data;
  10. 		}
  11. 	}
  12.  
  13. 	public static void main(String[] args){
  14. 		int[] arr = new int[]{12, 1, 2, 3, 0, 11, 4};
  15. 		System.out.println("Input array");
  16. 		for(int i: arr)
  17. 			System.out.print(i+",");
  18.  
  19. 		Node dummyNode = new Node(-Integer.MAX_VALUE);
  20. 		int[] countSmaller = new int[arr.length];
  21. 		for(int i=arr.length-1;i>=0;i--){
  22. 			Node node = new Node(arr[i]);
  23. 			push(node,dummyNode);
  24. 			countSmaller[i] = node.smallerCount;
  25. 		}
  26.  
  27. 		System.out.println("\nOutput array");
  28. 		for(int i: countSmaller)
  29. 			System.out.print(i+",");
  30. 		System.out.println("");
  31. 	}
  32.  
  33. 	private static void push(Node node, Node head){
  34. 		if(head != null){
  35. 			if(head.data < node.data){
  36. 				head.count++;
  37. 				//System.out.println("head.data="+head.data);
  38. 				node.smallerCount += (head.left == null)?1:(head.left.count+2);
  39. 				if(head.right == null){
  40. 					node.smallerCount--;	//to account for dummy node;
  41. 					//System.out.println(node.data+" - number of smaller elements on right >>"+node.smallerCount);
  42. 					head.right = node;
  43. 				} else{
  44. 					push(node, head.right);
  45. 				}
  46. 			} else if(head.data > node.data){
  47. 				head.count++;
  48. 				if(head.left == null){
  49. 					head.left = node;
  50. 					node.smallerCount--;	//to account for dummy node;
  51. 					//System.out.println(node.data+" - number of smaller elements on right >>"+node.smallerCount);
  52. 				} else{
  53. 					push(node,head.left);
  54. 				}
  55. 			}
  56. 		}
  57. 	}
  58. }
Success #stdin #stdout 0.13s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input array
12,1,2,3,0,11,4,
Output array
6,1,1,1,0,1,0,
https://ideone.com/QtAjCa
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!