Number of NGEs to the right |  ; use of stl stack in c ++ ; push the ( n - 1 ) th index to the stack ; traverse in reverse order ; if no element is greater than arr [ i ] the number of NGEs to right is 0 ; number of NGEs to right of arr [ i ] is one greater than the number of NGEs to right of higher number to its right ; reverse again because values are in reverse order ; returns the vector of number of next greater elements to the right of each index . ; Driver code ; query 1 answered ; query 2 answered ; query 3 answered
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > no_NGN ( int arr [ ] , int n ) { vector < int > nxt ; stack < int > s ; nxt . push_back ( 0 ) ; s . push ( n - 1 ) ; for ( int i = n - 2 ; i >= 0 ; i -- ) { while ( ! s . empty ( ) && arr [ i ] >= arr [ s . top ( ) ] ) s . pop ( ) ; if ( s . empty ( ) ) nxt . push_back ( 0 ) ; else nxt . push_back ( nxt [ n - s . top ( ) - 1 ] + 1 ) ; s . push ( i ) ; } reverse ( nxt . begin ( ) , nxt . end ( ) ) ; return nxt ; } int main ( ) { int n = 8 ; int arr [ ] = { 3 , 4 , 2 , 7 , 5 , 8 , 10 , 6 } ; vector < int > nxt = no_NGN ( arr , n ) ; cout << nxt [ 3 ] << endl ; cout << nxt [ 6 ] << endl ; cout << nxt [ 1 ] << endl ; return 0 ; }