Design a stack that returns its minimum element in O(1).

How to think about it

The interviewer is testing whether you can trade a little space to make an expensive query cheap. The naive get_min() scans the whole stack — O(n) every call. They want O(1), and the only way to get there is to stop computing the minimum on demand and instead keep it always ready. The real skill being probed is “maintain an aggregate incrementally,” the same instinct behind a running max in a sliding window.

Here’s the move. You carry a second stack alongside the main one, the same height at all times. Every time you push a value, you also push the minimum as of that moment — which is just min(new value, whatever was already on top of the min stack). So each level of the min stack remembers the smallest element that existed when that level was the top. Now get_min() is simply min_stack[-1], a constant-time peek. The beautiful part is the pop: when you pop both stacks together, the min stack automatically reveals the minimum from before that push, because that older minimum was never overwritten — it was sitting one level down the whole time.

A worked example

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        current_min = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(current_min)   # remember the min at this level

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()                 # pop both together, always in sync

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

    def get_min(self):
        return self.min_stack[-1]            # O(1) peek, no scan

ms = MinStack()
ms.push(5)            # stack=[5]      min=[5]
ms.push(3)            # stack=[5,3]    min=[5,3]
ms.push(7)            # stack=[5,3,7]  min=[5,3,3]  <- 7 did not lower the min
print(ms.get_min())   # 3
ms.pop()              # drop the 7
print(ms.get_min())   # 3  (the 7 never was the min)
ms.pop()              # drop the 3
print(ms.get_min())   # 5  (min restored to before 3 was pushed)

3
3
5

Follow the third push. Pushing 7 records min(7, 3) = 3, so the min stack holds [5, 3, 3] — the 7 left the minimum untouched. When you pop it, the min stack drops back to [5, 3] and still reports 3. Pop again and the min stack becomes [5], correctly restoring 5 as the minimum. The old minimums were never recomputed; they were preserved underneath, ready to resurface exactly when the elements above them disappeared.