Find the greater element

#1

can you briefly explain how using stack helps us to reduce time complexity…

#2

Naive approach would be to loop through every element and find the next greatest element one by one the time complexity would be o(n^n) as for n elements we have to traverse n times

let us see the stack based approach , here what we will do is twist our logic and instead of finding next greater element , we will find for every element for whom that element is next greater element , here we will utilize the propery of stack i.e LIFO , it will be more clear with the algo .
This the algo for stack based approach : -

  • Push the first element to stack.
  • Pick rest of the elements one by one and follow the following steps in loop.
    1. Mark the current element as next .
    2. If stack is not empty, compare top element of stack with next .
    3. If next is greater than the top element,Pop element from stack. next is the next greater element for the popped element.
    4. Keep popping from the stack while the popped element is smaller than next . next becomes the next greater element for all such popped elements
  • Finally, push the next in the stack.
  • After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.
    example :-
    1161×1253 73 KB

here notice that every element is pushed only once in the stack and popped only once out of the stack so if there are n elements so total number of stack operation would be 2*n (n times push and n times pop) so the time complexity is o(n)

Try to implement this algo yourself , In case of any doubt feel free to ask :slight_smile:

#3

in the example next greater element for 3 is -1 but according to the question i should be 11 as array is circular

#4

in the example next greater element for 3 is -1 but according to the question it should be 11 as array is circular

#5

@soorya19k, yes the above approach i have shared is for normal array ,
for circular array i have explained the approch in this discussion :- Find the greater element question
the concept is same you just need one more pass throught the array from starting and the time complexity will be same i.e o(n)