Stack Get Minimum In Const Time And Space Hint

#1

we do this question like that if element are
4 2 1 6 2 0 and mantain are min stack
4 2 1 1 1 0 then find min element
without this algorithm ?

#2

you know name of scientist who discoved this algorithm

#3

Hello @khemchandrs

The algorithm other than this could be like this
Suppose we have a stack like
4 5 6 3 4 1
Then what we can do is maintain a variable “min” and push the min - integer into the stack
Like this
4 came
4 is the min
push 4 - 4 = 0
5 came
push 4 - 5 = -1 in the stack
6 came
push 4 - 6 = -2 in the stack
3 came
push 4 - 3 = 1 in the stack
make 3 as the min
4 came
push 3 - 4 = -1 in the stack
1 came
push 3 - 1 = 2 in the stack
make 1 as the min

The stack is now 0 -1 -2 1 -1 2
Now inside the stack each positive element represents that here the min element has changed
How can we recover all the original numbers and the minimum element is
our “min” variable has 1 as the value in it.

First element is 2 => change in min element
new min element is 1 + 2 = 3 and the minimum here is 1
second element is -1
element is 3 - (-1) = 4 and minimum here is 3
third element is 1 => change in min element
new min element is 3 + 1 = 4 and the minimum here is 3
fourth element is -2
element is 4 - (-2) = 6 and minimum here is 4
…

This is the way you can solve this.

If you still need any help or the code for the problem, leave a reply and I will help you out.

#4

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.