Min Stack

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Examples

The brute-force approach

Use a regular stack for push/pop/top. For getMin(), scan the entire stack every time to find the smallest element.

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

    def push(self, val): self.stack.append(val)
    def pop(self):       self.stack.pop()
    def top(self):       return self.stack[-1]

    def get_min(self):
        return min(self.stack)    # ← O(n) scan every call

getMin() scanning the whole stack on every call is O(n). The problem requires all four operations to be O(1).

Spotting the pattern

This is a Stack problem. The key question to ask yourself:

Can I store the current minimum alongside each pushed element so I always know it without scanning?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.