min stack in O(1)

For those who want to know the intuition behind the "2 * ME - Y" that he was talking about (Sorry if it's too long):

So we need to find a way to encode the new minimum element with the previous minimum element and then update the minimum element with the new one. After we encode the two mins using a special formula, if later a pop operation comes in which this encoded number is at the top, it means we've to remove the new min from stack and as we stored separately, we can get back the previous min from this encoded number.

The simplest way you can encode the new min with the previous min is a linear combination of them both, as in, push some "c1 * new_min + c2 * prev_min (where c1 and c2 are some integers).

But there's a small catch. We need to ensure that our encoded number is less than the new min, because we need to know as to when do we have to remove the new min and retrieve the previous one. The best way to know is to see if the current stack top has a value smaller than the new minimum. It should technically be impossible that an element in stack is smaller than the new minimum, because if it was, then our new minimum would've been that element instead (I hope it's not too confusing lol).

So we need to reach this point:
c1 * new_min + c2 * prev_min < new_min (so the equation to the LHS is our encoding formula)

If c1 * new_min + c2 * prev_min is our formula for encoding the 2 numbers, what's our decoding formula? As in, when we've to pop this encoded number, how we get the previous minimum? We simply do this: rearrange the equation

encoded_number = c1 * new_min + c2 * prev_min

to

prev_min = (encoded number - c1 * min) / c2    or    (c1 * min - encoded number) / -c2

As a good programmer, you need to understand that even if at a large scale it may not matter, but it's better to assign c2 as -1 (For 2nd decoding formula) or 1 (for 1st decoding formula) so that we don't have to do any extra division while decoding back. We'll see whether c2 becomes -1 or 1 based on the encoding formula we generate, and then accordingly the decoding formula will be known.

So now we've to only find what is c1 and create a formula which has c2 = 1 or c2 = -1.

We know that

new_min < prev_min.

We can change new_min to 2 * new_min - new_min:

2 * new_min - new_min < prev_min

Then we rearrange to get:

2 * new_min - prev_min < new_min    (which is the way we wanted our formula to be)

So our c1 = 2 and c2 = -1. And since c2 = -1, our decoding formula will be the 2nd one above.

And that's why we push that (2 * ME - Y) number on stack. I hope this clears up the intuition behind the formula.

If you don't care about division's time complexity, you can generate your own c1 and c2 like this by playing with the values and starting from new_min < prev_min and getting the inequation of that type which I said above.