is the stack approach better than naive approach as in that too in the worst case we could traverse the whole stack of length n and thus O(n2) will be the TC?
Related to the approach
yes it is
**Time Complexity of stack based approach ** : O(n). It seems more than O(n) at first look. If we take a closer look, we can observe that every element of the array is added and removed from the stack at most once. So there are total 2n operations at most. Assuming that a stack operation takes O(1) time, we can say that the time complexity is O(n).
whereas for naive approach the time complexity is O( n ^ 2)