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...
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.
Sarah Jenkins is a veteran tech journalist with over 12 years of experience covering artificial intelligence, mobile innovations, and digital ethics. Her insights have appeared in leading technology publications worldwide.
