Number of NGEs to the right | Java program to print number of NGEs to the right ; array to store the next greater element index ; Use stack ; push the 0 th index to the stack ; traverse in the loop from 1 - nth index ; iterate till loop is empty ; get the topmost index in the stack ; if the current element is greater then the top index - th element , then this will be the next greatest index of the top index - th element ; initialize the cur index position 's  next greatest as index ; pop the cur index as its greater element has been found ; if not greater then break ; push the i index so that its next greatest can be found ; iterate for all other index left inside stack ; mark it as - 1 as no element in greater then it in right ; function to count the number of next greater numbers to the right ; initializes the next array as 0 ; calls the function to pre - calculate the next greatest element indexes ; if the i - th element has no next greater element to right ; Count of next greater numbers to right . ; answers all queries in O ( 1 ) ; returns the number of next greater elements to the right . ; driver code ; calls the function to count the number of greater elements to the right for every element . ; query 1 answered ; query 2 answered ; query 3 answered
import java . util . * ; class GFG { static void fillNext ( int next [ ] , int a [ ] , int n ) { Stack < Integer > s = new Stack < Integer > ( ) ; s . push ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) { while ( s . size ( ) > 0 ) { int cur = s . peek ( ) ; if ( a [ cur ] < a [ i ] ) { next [ cur ] = i ; s . pop ( ) ; } else break ; } s . push ( i ) ; } while ( s . size ( ) > 0 ) { int cur = s . peek ( ) ; next [ cur ] = - 1 ; s . pop ( ) ; } } static void count ( int a [ ] , int dp [ ] , int n ) { int next [ ] = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) next [ i ] = 0 ; fillNext ( next , a , n ) ; for ( int i = n - 2 ; i >= 0 ; i -- ) { if ( next [ i ] == - 1 ) dp [ i ] = 0 ; else dp [ i ] = 1 + dp [ next [ i ] ] ; } } static int answerQuery ( int dp [ ] , int index ) { return dp [ index ] ; } public static void main ( String args [ ] ) { int a [ ] = { 3 , 4 , 2 , 7 , 5 , 8 , 10 , 6 } ; int n = a . length ; int dp [ ] = new int [ n ] ; count ( a , dp , n ) ; System . out . println ( answerQuery ( dp , 3 ) ) ; System . out . println ( answerQuery ( dp , 6 ) ) ; System . out . println ( answerQuery ( dp , 1 ) ) ; } }