Find the greater element

#1

is there any way to solve this question in less than O(n^2), I am not able to use stack or queue here

#2

Hi @sktg99
Stack approach :

  1. Push the index of first element to stack.
  2. Pick rest of the index one by one and follow the following steps in loop.
    a. Mark the current index as next.
    b. If stack is not empty, compare arr[top element of stack] with arr[next].
    c. If arr[next] is greater than the arr[top element], store ans[top element]=arr[next]. Pop element from stack. arr[next] is the next greater element for the popped element.
    d. Keep popping from the stack while the arr[popped element] is smaller than arr[next]. arr[next] becomes the next greater element for all such popped elements
  3. Finally, push the next in the stack.
  4. After the loop in step 2 is over, pop all the remaining elements from stack and enter them into another stack.
  5. Repeat the above procedure in second stack.
  6. pop the remaining elements in second stack and store -1 for them.

Hope it helps
Mark resolved if satisfied :slight_smile:

#3

can u dry run that for the input 3 2 1 pls

#4

im not getting this logic

#5

???
???