Min Stack#

Problem#

Design a stack that supports the usual push, pop, and top operations plus a get_min operation that returns the smallest element currently in the stack. Every operation should run in constant time.

Example#

Push 3, push 5, get_min returns 3. Push 2, get_min returns 2. Pop, and get_min returns 3 again. Push 1, get_min returns 1.

Brute force#

Keep a single stack and scan it on every get_min call. That makes get_min O(n), which fails the constant-time requirement.

Optimal approach#

Store the running minimum next to each value. Each stack entry is a pair: the value pushed and the smallest value seen up to and including that push. When you push, the new minimum is min(new_value, current_min). When you pop, the previous minimum is automatically restored because it lives in the entry now on top. get_min just reads the second field of the top entry, all in O(1).

Solution#

 1class MinStack:
 2    def __init__(self):
 3        self._stack = []  # list of (value, min_so_far)
 4
 5    def push(self, value: int) -> None:
 6        current_min = value
 7        if self._stack:
 8            current_min = min(value, self._stack[-1][1])
 9        self._stack.append((value, current_min))
10
11    def pop(self) -> None:
12        self._stack.pop()
13
14    def top(self) -> int:
15        return self._stack[-1][0]
16
17    def get_min(self) -> int:
18        return self._stack[-1][1]
19
20
21stack = MinStack()
22stack.push(3)
23stack.push(5)
24print(stack.get_min())  # 3
25stack.push(2)
26print(stack.get_min())  # 2
27stack.pop()
28print(stack.get_min())  # 3

Complexity#

• Time: O(1) for every operation.
• Space: O(n) to hold n paired entries.

Review the stacks and queues topic for more stack design questions, then continue the 60-day challenge.