Answers for "previous greater element"

C++
0

previous greater element

//program in C++ to find previous greater element

//following approach is better than naive approach because it does very less no.
//of comparisons between elements and skips unnecessary comparisons

#include <iostream>
#include <stack>
using namespace std;

void find_pge(int a[],int pge[],int n){
    stack<int> s;
    for(int i=n-1;i>=0;i--){
      		//if current element is greater than top of stack
            while(!s.empty() && a[s.top()] < a[i]){
                pge[s.top()] = a[i];
                s.pop();
            }
            s.push(i);
    }
   //mark all remaining element's previous greater element to be -1(not present)
    while(!s.empty()){
        pge[s.top()] = -1;
        s.pop();
    }
}

int main() {
	int a[5] = {5,4,3,4,5},pge[5];
	find_pge(a,pge,5);
	for(int i=0;i<5;i++){
	    cout<<"previous greater element for "<<a[i]<<" is "<<pge[i]<<"\n";
	}
	return 0;
}
Posted by: Guest on September-22-2021

Browse Popular Code Answers by Language