Min Element of Stack for all iteration

Question

Hello

I got a problem statement today which has one function taking argument as stack of int.... What i need to do is to print min element present into stack post each pop operation....

As we cannot iterate over stack, how to achieve this in min time complexity?

I just got confused with this problem statement. I don't need full source code for this...Can anyone give some idea to implement this?

Expected is O(N) as per problem statement.

Answer 1

keep 2 stacks, one original stack1 where you will push all elements and another stack2 for potential minimum elements.
push 1st element in both stacks, and for all other elements push into stack2 only when element is <= stack2.top().
In pop() operation, remove element from stack2 also if it is equal to stack2.top()

For minimum element, that will be stack2.top().

It will take O(1) time for each query(push, pop, min element etc) but extra O(n) space.

Its a standard problem I think, maybe more optimized solution taking extra O(1) space only exists.

Answer 2

I don't know if this is the fastest way but you can try this:
pop from stack1, assign it to min and push it to stack2
continue doing this until stack1 is empty but only assign if current is smaller than min
after you find min element, put stack1's items back to it

Answer 3

Yeah I thought you were trying to find min once.
Maybe you could try writing a recursive function so you can find the first min while you're also finding others.
I made something that prints your output in reverse order. I can post it if you want. But I'll wait until you tell me because you might want to try it yourself first.

Answer 4

https://code.sololearn.com/cAY4S5l1eJPC/?ref=app
I made something like this but i don't know how to reverse the output. It's also probably closer to being O(n)

Answer 5

Thanks Mert Yazıcı for your help.. I am surprised how recursive is helping here... Could you plz share code to have a look on it once ?

Gaurav Agrawal , thanks for your help...I tried and updated code but it is not giving me proper output... Will try this and debug to make it happen in some time....

Answer 6

Yeah at least I started code with this logic as below :

https://code.sololearn.com/c0SHvv61CM9i/?ref=app

But it has additional space as O(N) and time complexity as O(N*N)....Right ?

Answer 7

I updated my code now to have correct output... I was missing to do stack reverse earlier

Mert Yazıcı , you may have entry in stack (rather than direct print by cout) and print stack as it reverse the input...