why it is O(N) , there is possiblity that for any index i we don’t have a prev largest element, that time we have to pop every number from stack until it becomes empty.
therefore time complexity should be in order of N^2.
ex: [ 10 8 9 50 ] ,
for 50 all the prev number (9,8,10) should be popped from stack. But sir said that there will be only 1 push or 1 pop for any index?
You must note that each element is pushed into the stack atmost once and also popped out atmost once.
Pushing and popping are O(1) operations.
So complexity would be O(2n) which is equivalent to O(n)
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.