Coding interview problems › Stack & Monotonic Stack

📚 Stack & Monotonic Stack Medium

Min Stack

Min Stack explained: store the running minimum next to every value so push, pop, top and getMin are all O(1). Tested Python, pitfalls and a live stack visual.

Also searched as: stack with getMin in O(1) · design a min stack · special stack with minimum

📚

Try it live Free

Stacks & the Monotonic Stack

Use the stack mode to watch pushes and pops happen only at the top; this design adds one extra field to every pushed entry, the minimum so far.

Open the playground →

The problem

Design a stack that supports push(x), pop(), top() and get_min(), where get_min returns the smallest element currently in the stack. Every operation must take O(1) time. You may assume pop, top and get_min are only called on a non-empty stack.

Inputpush(5), push(2), push(7), get_min(), pop(), pop(), get_min()
Output2, then 5

Once 2 is popped, the minimum goes back to 5.

The key insight

The trouble is that popping the current minimum should reveal the previous minimum. So remember it: store each value together with the minimum of the stack at the moment it was pushed. The top entry then always carries the current minimum.

Brute force first: Scanning the whole stack inside get_min works but makes that operation O(n).

Step-by-step approach

  1. Keep one list of pairs (value, min_so_far).
  2. On push(x), the new minimum is x if the stack is empty, else min(x, current_min); append (x, new_min).
  3. pop() removes the top pair; the pair below it already holds the older minimum.
  4. top() returns the value of the top pair, and get_min() returns its stored minimum.

Python solution

PYTHON 3tested
class MinStack:
    def __init__(self):
        self.items = []                     # (value, min of stack so far)

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

    def pop(self):
        return self.items.pop()[0]

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

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

Complexity

TimeO(1) per operation
SpaceO(n)

Each operation touches only the top of the list. Storing a minimum with every element doubles the memory but keeps it O(n).

Common mistakes

Frequently asked questions

What is the time and space complexity of a Min Stack?

All four operations are O(1) time. Space is O(n), since each element also stores the minimum at the time it was pushed.

Can I do it with less extra memory?

A second stack that only records a value when it is less than or equal to the current minimum uses less memory on typical inputs. A trickier approach stores encoded differences to use O(1) extra space, but it is error-prone in interviews.

How would I build a Max Stack?

Use the same idea with max instead of min. Supporting popMax as well needs a heavier structure such as a doubly linked list plus a sorted container.

Why is this considered a design question?

The task is to choose what to store so every operation stays O(1). Interviewers look for the insight that each element can carry a summary of everything beneath it.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Stack & Monotonic Stack Stacks & the Monotonic Stack lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.