There is a similar question on gfg which has a method using stacks but it is for regular array. What is the best solution for this?
What is the optimal solution for this?
Hey @tusharnitharwal
The stack approach is as follows:
Push the index of first element to stack.
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
Finally, push the next in the stack.
After the loop in step 2 is over, pop all the remaining elements from stack and enter them into another stack.
Repeat the above procedure in second stack.
pop the remaining elements in second stack and store -1 for them.
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.