Stack getminimum doubt

#1

how 3 is the current min in the end
shouldn’t it be 3

why are we doing this actually?

i am not really getting our motive to do this approach

#2

@yatin
I am not able to understand what you mean by " how 3 is the current min in the end
shouldn’t it be 3 ". Please elaborate a bit what you are trying to say.

As for why we are doing this , if we wish to get the minimum element in the stack so far , there are multiple methods to do so . But all of them would either require extra space or extra time or both. This is the best method as it does not require either. Hence this is the best method to do it.

I request you to take a look at my code. The algorithm and implementation is entirely same , it’s just that my program is a bit more flexible and you might be able to grasp the essence of this in it.
My code - https://ide.codingblocks.com/s/110036

1 Like
#3

aren’t we trying to find the min no in the stack?
that we can also find by keep a variable min_element and keep updating it and continuously push the elements

#4

@yatin
This would only work if you are only pushing elements into the stack and never popping any. However if we start popping the elements from the stack , this will not work as when you pop your min element. How will you find out what’s the next smallest element in the stack in O(1) time and space ?

1 Like
#5

so we need to find the smallest element after every insertion and every pop???
is that the motive sir?

#6

@yatin
Yes , that is the motive. We could be asked to push or pop an element anytime during the run of the program. Also at any instant we could be asked to print the minimum element in the stack so far.
If you take a look at my code , it runs on queries so elements can be pushed or popped during runtime and we would need to compute the minimum everytime again and again.
With any other method it would require more time and/or space. This is the best method as it does this in O(1) time and space.

1 Like
#7

ok sir got it thank u :slight_smile: