Count of Array elements greater than all elements on its left and at least K elements on its right | Java program to implement the above appraoch ; Structure of an AVL Tree Node ; Size of the tree rooted with this Node ; Helper class to pass Integer as referencee ; Utility function to get height of the tree rooted with N ; Utility function to find size of the tree rooted with N ; Utility function to get maximum of two integers ; Utility function to right rotate subtree rooted with y ; Perform rotation ; Update heights ; Update sizes ; Return new root ; Utility function to left rotate subtree rooted with x ; Perform rotation ; Update heights ; Update sizes ; Return new root ; Function to obtain Balance factor of Node N ; Function to insert a new key to the tree rooted with Node ; Perform the normal BST rotation ; Update count of smaller elements ; Update height and size of the ancestor ; Get the balance factor of the ancestor ; Left Left Case ; Right Right Case ; Left Right Case ; Right Left Case ; Function to generate an array which contains count of smaller elements on the right ; Insert all elements in the AVL Tree and get the count of smaller elements ; Function to find the number of elements which are greater than all elements on its left and K elements on its right ; Stores the count of smaller elements on its right ; Driver Code
class GFG { static class Node { int key ; Node left ; Node right ; int height ; int size ; public Node ( int key ) { this . key = key ; this . left = this . right = null ; this . size = this . height = 1 ; } } ; static class RefInteger { Integer value ; public RefInteger ( Integer value ) { this . value = value ; } } static int height ( Node N ) { if ( N == null ) return 0 ; return N . height ; } static int size ( Node N ) { if ( N == null ) return 0 ; return N . size ; } static int max ( int a , int b ) { return ( a > b ) ? a : b ; } static Node rightRotate ( Node y ) { Node x = y . left ; Node T2 = x . right ; x . right = y ; y . left = T2 ; y . height = max ( height ( y . left ) , height ( y . right ) ) + 1 ; x . height = max ( height ( x . left ) , height ( x . right ) ) + 1 ; y . size = size ( y . left ) + size ( y . right ) + 1 ; x . size = size ( x . left ) + size ( x . right ) + 1 ; return x ; } static Node leftRotate ( Node x ) { Node y = x . right ; Node T2 = y . left ; y . left = x ; x . right = T2 ; x . height = max ( height ( x . left ) , height ( x . right ) ) + 1 ; y . height = max ( height ( y . left ) , height ( y . right ) ) + 1 ; x . size = size ( x . left ) + size ( x . right ) + 1 ; y . size = size ( y . left ) + size ( y . right ) + 1 ; return y ; } static int getBalance ( Node N ) { if ( N == null ) return 0 ; return height ( N . left ) - height ( N . right ) ; } static Node insert ( Node Node , int key , RefInteger count ) { if ( Node == null ) return ( new Node ( key ) ) ; if ( key < Node . key ) Node . left = insert ( Node . left , key , count ) ; else { Node . right = insert ( Node . right , key , count ) ; count . value = count . value + size ( Node . left ) + 1 ; } Node . height = max ( height ( Node . left ) , height ( Node . right ) ) + 1 ; Node . size = size ( Node . left ) + size ( Node . right ) + 1 ; int balance = getBalance ( Node ) ; if ( balance > 1 && key < Node . left . key ) return rightRotate ( Node ) ; if ( balance < - 1 && key > Node . right . key ) return leftRotate ( Node ) ; if ( balance > 1 && key > Node . left . key ) { Node . left = leftRotate ( Node . left ) ; return rightRotate ( Node ) ; } if ( balance < - 1 && key < Node . right . key ) { Node . right = rightRotate ( Node . right ) ; return leftRotate ( Node ) ; } return Node ; } static void constructLowerArray ( int arr [ ] , RefInteger [ ] countSmaller , int n ) { int i , j ; Node root = null ; for ( i = 0 ; i < n ; i ++ ) countSmaller [ i ] = new RefInteger ( 0 ) ; for ( i = n - 1 ; i >= 0 ; i -- ) { root = insert ( root , arr [ i ] , countSmaller [ i ] ) ; } } static int countElements ( int A [ ] , int n , int K ) { int count = 0 ; RefInteger [ ] countSmaller = new RefInteger [ n ] ; constructLowerArray ( A , countSmaller , n ) ; int maxi = Integer . MIN_VALUE ; for ( int i = 0 ; i <= ( n - K - 1 ) ; i ++ ) { if ( A [ i ] > maxi && countSmaller [ i ] . value >= K ) { count ++ ; maxi = A [ i ] ; } } return count ; } public static void main ( String [ ] args ) { int A [ ] = { 2 , 5 , 1 , 7 , 3 , 4 , 0 } ; int n = A . length ; int K = 3 ; System . out . println ( countElements ( A , n , K ) ) ; } }