This problem follows the Auxiliary Stack pattern, commonly found in the Stack category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Maintain a parallel stack that tracks the current minimum at each level.
The min stack only grows when a new minimum is seen — it mirrors the main stack's minimum at each depth level.
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val):
self.stack.append(val)
if not self.minStack or val <= self.minStack[-1]:
self.minStack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.minStack[-1]:
self.minStack.pop()
def getMin(self):
return self.minStack[-1]Practice Min Stack and similar Stack problems with flashcards. Build pattern recognition through active recall.
Practice this problem