Find the greater element (another approach)

#1

code: https://ide.codingblocks.com/s/88814
Currently, I am solving this question O(n2) and I want to know is there any optimisation for the solution using stacks.

#2

@sid.pahuja hey siddharth pahuja try with stack, using stack complete this implement in o(n)

#3

can you help me with the approach. I am unable to figure it out

#4

@sid.pahuja hey siddharth
first take a input array
and a stack< int > s;
push the first index of array into the stack like s.push(a[0]);
apply loop from i=1 to n
now apply a while loop
while(!s.empty()&&s.top()<a[ i ])
{
cout<<a[ i ]<<" “;
now pop the current element from the stack reason for that we want to check for next element
s.pop();
}
push the next element of the array according to loop
s.push( a[ i ] );
while(! s.empty() )
{
cout<<-1<<” ";
s.pop();
}

#5

here you are applying a for loop and inside it a while loop so how is the complexity O(n).

#6

@sid.pahuja don’t confuse there is only one while block which going to operate over the stack. "the statement now apply a while loop I wrote this for understanding purposes " so basically there is having two operations the first one pushing the value into the stack and the second one working on the stored value in the stack.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

can u please elaborate on how is the complexity O(N) ??

#9

can u tell how is the complexity o(n) ??