mycsmajor
Data structures problem 21 of 30

Min stack

  • Data structures
  • Medium

Design a stack class with push(x), pop(), top() and get_min(), where every operation runs in O(1) time.

s = MinStack()
s.push(5)
s.push(2)
s.push(7)
s.get_min()   # 2
s.pop()       # 7
s.pop()       # 2
s.get_min()   # 5
Show hint

Keep a second stack that records, for each level of the main stack, the minimum so far.

Show solution 
class MinStack:
    def __init__(self):
        self.items = []
        self.mins = []

    def push(self, x):
        self.items.append(x)
        smallest = x if not self.mins else min(x, self.mins[-1])
        self.mins.append(smallest)

    def pop(self):
        self.mins.pop()
        return self.items.pop()

    def top(self):
        return self.items[-1]

    def get_min(self):
        return self.mins[-1]

A single "current minimum" variable breaks when you pop the minimum, because you no longer know the one before it. The second stack remembers the minimum at every depth, so popping just restores the previous answer. It trades O(n) extra memory for O(1) time.

Want a problem like this every day? See today's problem and keep a streak going.