Number of NGEs to the right |  ; array to store the next greater element index ; use of stl stack in c ++ ; 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 program to test the above function ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void fillNext ( int next [ ] , int a [ ] , int n ) { stack < int > s ; s . push ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) { while ( ! s . empty ( ) ) { int cur = s . top ( ) ; if ( a [ cur ] < a [ i ] ) { next [ cur ] = i ; s . pop ( ) ; } else break ; } s . push ( i ) ; } while ( ! s . empty ( ) ) { int cur = s . top ( ) ; next [ cur ] = -1 ; s . pop ( ) ; } } void count ( int a [ ] , int dp [ ] , int n ) { int next [ n ] ; memset ( next , 0 , sizeof ( next ) ) ; 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 ] ] ; } } int answerQuery ( int dp [ ] , int index ) { return dp [ index ] ; } int main ( ) { int a [ ] = { 3 , 4 , 2 , 7 , 5 , 8 , 10 , 6 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int dp [ n ] ; count ( a , dp , n ) ; cout << answerQuery ( dp , 3 ) << endl ; cout << answerQuery ( dp , 6 ) << endl ; cout << answerQuery ( dp , 1 ) << endl ; return 0 ; }