Count of Array elements greater than all elements on its left and next K elements on its right | C ++ Program to implement the above approach ; Function to print the count of Array elements greater than all elements on its left and next K elements on its right ; Iterate over the array ; If the stack is not empty and the element at the top of the stack is smaller than arr [ i ] ; Store the index of next greater element ; Pop the top element ; Insert the current index ; Stores the count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countElements ( int arr [ ] , int n , int k ) { stack < int > s ; vector < int > next_greater ( n , n + 1 ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( s . empty ( ) ) { s . push ( i ) ; continue ; } while ( ! s . empty ( ) && arr [ s . top ( ) ] < arr [ i ] ) { next_greater [ s . top ( ) ] = i ; s . pop ( ) ; } s . push ( i ) ; } int count = 0 ; int maxi = INT_MIN ; for ( int i = 0 ; i < n ; i ++ ) { if ( next_greater [ i ] - i > k && maxi < arr [ i ] ) { maxi = max ( maxi , arr [ i ] ) ; count ++ ; } } return count ; } int main ( ) { int arr [ ] = { 4 , 2 , 3 , 6 , 4 , 3 , 2 } ; int K = 2 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countElements ( arr , n , K ) ; return 0 ; }