AI Hints
Home›DSA in Python Tutorial›Designing Data Structures
DSA in Python · Lesson 113 of 132

Practice: Min Stack

The minimum in O(1).

⏱ 2 min read▶ Video at 2:15:00🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Design a stack with push, pop, and one extra operation. Get min, which returns the smallest item in the stack, in O of one. Searching the stack would be O of N. Pause. What could you store alongside each item?

Practice: Min Stack
From the video: Practice: Min Stack
  • push and pop
  • Plus get_min
  • All in O(1)

Store the minimum so far

The trick is to push pairs. Each item, together with the smallest value at that point. So the minimum is always on top, right next to the newest item. When we pop, the old minimum comes back automatically. Run it. The minimum goes from one, back to two.

min_stack.pypython
class MinStack:
    def __init__(self):
        self.items = []
    def push(self, x):
        smallest = min(x, self.items[-1][1]) if self.items else x
        self.items.append((x, smallest))
    def pop(self):
        return self.items.pop()[0]
    def get_min(self):
        return self.items[-1][1]

s = MinStack()
for x in [5, 2, 8, 1]:
    s.push(x)
print("min:", s.get_min())
s.pop()
print("min after pop:", s.get_min())
Output
min: 1
min after pop: 2

Trading space for time

This is a common design pattern. We store a little extra information with each item, so a question that would need a search becomes a simple lookup. It doubles the memory, but every operation is O of one. The same idea works for a max stack.

keyvalue
Pushstore (item, min so far)
Popold min returns
get_mintop of the stack
CostO(1), extra memory

Summary

Store the minimum so far with every item, and the minimum is always on top. Next, finding the middle of numbers that keep arriving.

Key takeaways
  • Push pairs
  • Min is on top
  • O(1) everything
Next up: Practice: Median of a Stream — two heaps