Retrieving the minimum element in a stack at a constant time

Can you please help me understand what is going on in this line of code?

def push(self, x): self.stack.append(x) if len(self.minStack): if x < self.minStack[-1][0]: self.minStack.append([x, 1]) elif x == self.minStack[-1][0]: self.minStack[-1][1] += 1 else: self.minStack.append([x, 1]) 

it is taken from the line of this code:

class MinStack2: def __init__(self): self.stack, self.minStack = [], [] # @param x, an integer # @return an integer def push(self, x): self.stack.append(x) if len(self.minStack): if x < self.minStack[-1][0]: self.minStack.append([x, 1]) elif x == self.minStack[-1][0]: self.minStack[-1][1] += 1 else: self.minStack.append([x, 1]) 

You can also find it at this GitHub account:

Thank you in advance

Please, dont just mark it down if there is any misunderstanding for you. Leave a feedback rather. This is a plattform to learn and I feel like marking post down without an explanantion is very uneducated

1 Answer

Whenever you push onto the stack, you also check if this item is smaller than the previous minimum, which is kept on top of minStack, along with the count of how many of that item are in the stack.

If the item is smaller, then you push it (with a count of 1) onto minStack. If it's the same, you increment the count of that item by one.

Every time you pop an item, if it is the smallest item in the stack (i.e. == minStack[-1][0]), you decrement the count of the smallest item. If that count becomes zero, you pop the item off minStack. Now the smallest item in the stack is whatever it was before the first of that smaller item was added. This is because in order to discard that first instance of the smallest item, we had to pop everything on top of it first, essentially rolling the stack back to the point in time at which the smallest element was added.

PS: When you find yourself writing your own stack implementations, know that any stack that doesn't return the items it pops is acting very strangely.