CareerCup

use a balanced binary search tree, similar to geeksforgeeks.org/count-smaller-elements-on-right-side

public class SmallerOnRight {
	public static void updateCountSmaller(int[] elements, int[] smallerCount) {
		BSTNode root = new BSTNode(elements[0], 0);

		for (int i = 1; i < elements.length; i++) {
			BSTNode parent = null;
			BSTNode temp = root;
			while (temp != null) {
				if (temp.getData() > elements[i]) {
					parent = temp;
					updateSmallerCount(parent, smallerCount);
					temp = temp.getLeft();
					if (temp == null) {
						parent.setLeft(new BSTNode(elements[i], i));
					}
				} else {
					parent = temp;
					temp = temp.getRight();
					if (temp == null) {
						parent.setRight(new BSTNode(elements[i], i));
					}

				}
			}

		}
	}

	public static void updateSmallerCount(BSTNode parent, int[] smallerCount) {
		BSTNode runner = parent;
		while (runner != null) {
			smallerCount[runner.getIndex()] = smallerCount[runner.getIndex()] + 1;
			runner = runner.getRight();
		}

	}

	public static void main(String[] args) {
		int[] elements = new int[] { 12, 1, 2, 3, 0, 11, 4 };
		int[] smallerCount = new int[] { 0, 0, 0, 0, 0, 0, 0 };
		updateCountSmaller(elements, smallerCount);
	}

}

Why can't I just sort the array and do arraysize-current_element_index ? we can do it in o(N.logN).

// i think it is not match with the code complexcity but it is for those developer who are new and want to write simple and intersting code

Hope you will get it !

import java.util.Scanner;
  
  class Amazon1{
  
     public static void main(String s[]){
       Scanner sc = new Scanner(System.in);
        
         System.out.println("Enter the size of array");
         int a = sc.nextInt();
   
         int b[] = new int[a];
		 int c[] = new int[a];
         int i,j,k;
		 
		 System.out.println("Enter the number to be short");
		 
         for(i=0;i<a;i++){
			b[i] = sc.nextInt();
			c[i] = b[i];
         }		  
		 System.out.println("\n");
		 for(i=0;i<a;i++){
		    for(j=0;j<a;j++){
			if(b[i]>b[j]){
			 k=b[i];
			 b[i]=b[j];
			 b[j]=k;
			 }
			 }
			 }
			 for(i=0;i<a;i++){
			   System.out.println(c[i]+"\t"+b[i]);
			 }
	 }
}

// hey! developer this may be not code complexcity
but i develop this simple code for all those developer who are new
j
so ,just do it

import java.util.Scanner;
  
  class Amazon1{
  
     public static void main(String s[]){
       Scanner sc = new Scanner(System.in);
        
         System.out.println("Enter the size of array");
         int a = sc.nextInt();
   
         int b[] = new int[a];
		 int c[] = new int[a];
         int i,j,k;
		 
		 System.out.println("Enter the number to be short");
		 
         for(i=0;i<a;i++){
			b[i] = sc.nextInt();
			c[i] = b[i];
         }		  
		 System.out.println("\n");
		 for(i=0;i<a;i++){
		    for(j=0;j<a;j++){
			if(b[i]>b[j]){
			 k=b[i];
			 b[i]=b[j];
			 b[j]=k;
			 }
			 }
			 }
			 for(i=0;i<a;i++){
			   System.out.println(c[i]+"\t"+b[i]);
			 }
	 }
}	 

<-----output----->

input{ 22 1 33 4 55 2  8}


output
22         55
1           33
33         22
4            8
55          4
2            2
8            1