Can you please explain how it can be performed in O(1).
Quiz on Stacks and Queues
Hello Rahul, you haven’t mentioned the question about which ques you are talking about. But I think you are talking about min stack ques having O(1) time complexity.
So, yes the time complexity is O(1) you need to maintain the two stacks. In one stack you will use it as main stack from where you have to push,pop,top whatever element you are getting. And another stack you can name it as min stack. That will store the min ans of the every instant and from there you can return the top and that will be the min ans.
For an ex.
suppose I have nos. 2 4 5 3 1 6
And I will insert them into my stacks
Stack1 = {}, Stack2 = {} // empty stacks and we will consider the rightmost element as the top element
now insert 2
stack1 = {2} Stack2 = {2} // as both were empty so we need to insert the element in both of the stacks
now insert 4
stack1 = {2,4} but for stack 2 we can see that the top of the stack2 is less than the current element so we will again insert 2 in this Stack2 = {2,2} // we need to check if(Stack2.top() < curr) stack2.insert(stack2.top()) else stack2.insert(curr)
stack1 = {2,4,5} but for stack 2 we can see that the top of the stack2 is less than the current element so we will again insert 2 in this Stack2 = {2,2,2} // we need to check if(Stack2.top() < curr) stack2.insert(stack2.top()) else stack2.insert(curr)
stack1 = {2,4,5,3} but for stack 2 we can see that the top of the stack2 is less than the current element so we will again insert 2 in this Stack2 = {2,2,2,2} // we need to check if(Stack2.top() < curr) stack2.insert(stack2.top()) else stack2.insert(curr)
stack1 = {2,4,5,3,1} but for stack 2 we can see that now the curr is less than the top of that stack2 so this time we will insert the curr element, Stack2 = {2,2,2,1} // we need to check if(Stack2.top() < curr) stack2.insert(stack2.top()) else stack2.insert(curr)
stack1 = {2,4,5,3,1,6} but for stack 2 we can see that the top of the stack2 is less than the current element so we will again insert 1 in this Stack2 = {2,2,2,2,1,1} // we need to check if(Stack2.top() < curr) stack2.insert(stack2.top()) else stack2.insert(curr)
So this is how the stacks are working and if you see whenever we use the top element of the stack we can get the min ans of the stack. And in case of pop you need to pop the element from both the stacks whatever is the top element in that case.
I hope it is clear to you. In case it is clear to you pls mark it as resolve and provide the rating as well as feedback so that we can improve ourselves.
In case there is still some confusion pls let me know, I will surely try to help you out.
Thanks 
Happy Coding !!
1 Like
yes i was talking about that question and sorry about not mentioning the question number. Thanks for the explanation. I understood perfectly. Thanks for clearing my doubt.