For the outer loop we have n iterations, and for each iteration, there can be at max n iterations. So this would also give a complexity of o(n^2)
What is the time complexity of the optima solution?
No you are getting it in a wrong way, for outer loop you have n iterations but for inner while loop it is totally dependent upon the elements of the stack, and the elements of the stack are coming from the array elements itself.
So if you see it logically then, the every element at max will go into the array at once and come out of it once, so the number of operations for the inner loop is restricted and it doesn’t contribute any extra complexity.
So the optimized time complexity is O(N).
Feel free to ask if you have any furthur doubt in it.
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.