Skip to content

Volume ITechnology

4.8.2 — Min Stack ​

LeetCode 155 · Medium · ★ Blind 75

The problem ​

Design a stack with four operations, and make every one of them run in O(1) time, meaning a fixed number of steps no matter how big the stack gets.

  • push(val) puts val on top.
  • pop() removes the top item.
  • top() returns the top item without removing it.
  • getMin() returns the smallest item currently in the stack.
push(-2)
push(0)
push(-3)
getMin()  →  -3
pop()               (removes -3)
top()     →  0
getMin()  →  -2

Values can be negative, zero or positive. The problem promises that pop, top and getMin are only called when the stack is not empty. There are up to 30,000 calls in total.

What the problem is really asking ​

push, pop and top are what any stack already does in constant time. The new part is getMin.

Look at the example. After pop() removes −3, the minimum goes back to −2. So the stack must remember not only the current minimum, but what the minimum was before each push. The real question is: how do you undo a change to the minimum, instantly, when an item is popped?

The brute force, and where it wastes work ​

Keep a normal stack. For getMin, scan the whole stack.

python
def getMin(self):
    return min(self.stack)       # looks at every item

That is O(n) per call. Keeping one variable min_val, updated on each push, does not fix it either. When you pop the item that was the minimum, min_val is now wrong, and the only way to find the new minimum is to scan the stack again.

The waste in one sentence: every push already knew what the minimum was at that moment, but the brute force throws that knowledge away and recomputes it later.

The idea ​

Remember the minimum level by level, not once for the whole stack. Each item should carry a note saying "the smallest value from the bottom of the stack up to me". When that item is popped, its note goes with it, and the note on the new top item is exactly the correct minimum again.

Think of stacking boxes in a storeroom. On each box you stick a note: "the lightest box from the floor up to here weighs X". When you lift off the top box, its note leaves with it. To know the lightest box still in the pile, you just read the note on the new top box. You never look at the boxes underneath.

We keep those notes in a second stack, called mins, that moves in step with the main stack.

The solution ​

To save memory, this version only pushes onto mins when a value is a new minimum (or equal to it). The simpler version comes afterwards.

python
class MinStack:
    def __init__(self):
        self.stack = []                                   # (1)
        self.mins = []                                    # (2)

    def push(self, val: int) -> None:
        self.stack.append(val)                            # (3)
        if not self.mins or val <= self.mins[-1]:         # (4)
            self.mins.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.mins[-1]:             # (5)
            self.mins.pop()

    def top(self) -> int:
        return self.stack[-1]                             # (6)

    def getMin(self) -> int:
        return self.mins[-1]                              # (7)
ts
class MinStack {
  private stack: number[] = [];                           // (1)
  private mins: number[] = [];                            // (2)

  push(val: number): void {
    this.stack.push(val);                                 // (3)
    const n = this.mins.length;
    if (n === 0 || val <= this.mins[n - 1]) {             // (4)
      this.mins.push(val);
    }
  }

  pop(): void {
    if (this.stack.pop() === this.mins[this.mins.length - 1]) {  // (5)
      this.mins.pop();
    }
  }

  top(): number { return this.stack[this.stack.length - 1]; }     // (6)
  getMin(): number { return this.mins[this.mins.length - 1]; }    // (7)
}

Line by line ​

(1) The main stack. It holds every value, in the order pushed.

(2) The minimum stack. Its top is always the smallest value currently in the main stack. Underneath that are older minimums, waiting to come back when the newer ones are popped.

(3) Push onto the main stack. Every value goes here.

(4) Is this a new minimum? If mins is empty, this is the first value, so it is the minimum. If val is smaller than or equal to the current minimum, it also goes on mins. self.mins[-1] means "the last item of the list", which is the top of the stack.

(5) Pop, and undo the minimum if needed. self.stack.pop() removes the top value and hands it back. If that value equals the top of mins, then the value leaving was the current minimum. So we pop mins too, and the older minimum underneath becomes the top again.

(6) top. Read the last item of the main stack.

(7) getMin. Read the last item of mins. No scanning.

The <= that everybody gets wrong ​

Line (4) uses <=, not <. Here is what breaks with <.

  1. Push 2. mins is empty, so it becomes [2].
  2. Push 2 again. With <, the check 2 < 2 is false, so mins stays [2].
  3. Pop. The popped value is 2, which equals the top of mins, so mins is popped and becomes [].
  4. Now the main stack still holds a 2, but mins is empty. getMin crashes, or reports a wrong value if there was something underneath.

With <=, step 2 pushes the second 2 onto mins as well, giving [2, 2]. The pop in step 3 removes one of them, and mins is still [2], which is correct. Every copy of the current minimum needs its own entry in mins. This is the most common bug on this problem.

Trace ​

The example from the top: push −2, push 0, push −3, getMin, pop, top, getMin.

Callstack aftermins afterReturns
push(−2)[−2][−2]—
push(0)[−2, 0][−2] (0 is not ≤ −2)—
push(−3)[−2, 0, −3][−2, −3]—
getMin()unchangedunchanged−3
pop()[−2, 0][−2] (popped −3 equals top of mins)—
top()unchangedunchanged0
getMin()unchangedunchanged−2

The simpler version ​

If you would rather not think about <= at all, push the current minimum onto mins on every push.

python
def push(self, val):
    self.stack.append(val)
    if not self.mins:
        self.mins.append(val)
    else:
        self.mins.append(min(val, self.mins[-1]))   # the minimum up to this level

def pop(self):
    self.stack.pop()
    self.mins.pop()                                  # always pop both

Now both stacks always have the same height. pop needs no comparison, and there is no <= to get wrong. It uses more memory when the values keep rising, and the same memory when they keep falling. In an interview this is often the better first answer, because it is obviously correct. You can offer the memory-saving version afterwards.

Complexity, derived ​

Time. Every method does a fixed number of steps. Adding to or removing from the end of a Python list or a JavaScript array takes constant time, because no other items have to move. Reading [-1] jumps straight to the last item. There are no loops anywhere. So all four operations are O(1).

Space. The main stack holds n values. In the worst case, the values are pushed in falling order, like 5, 4, 3, 2, 1. Then every value is a new minimum and goes onto mins too. So mins can also hold n values. The total extra memory is O(n).

Edge cases ​

  • Rising values, like 1, 2, 3, 4. Only the 1 goes onto mins. This is where the memory-saving version helps.
  • Falling values, like 4, 3, 2, 1. Every value goes onto mins.
  • Repeated minimums, like 2, 2. Handled by <=, as shown above.
  • Negative values. Normal comparison handles them.

A version with no second stack ​

There is a trick that keeps the current minimum in one variable and no second stack. When a new minimum arrives, you store an encoded number, 2 * val - currentMin, instead of val. On pop, a stored number smaller than the current minimum tells you it was encoded, and you can work out the previous minimum from it.

It works, but in most languages it is a poor idea. The doubled number can grow too large for a fixed-size integer, and the code becomes hard to read. Python's integers never overflow, but the code is still hard to follow. Mention the trick, then say why you would not use it in real code.

Variations you will meet ​

The general idea is to carry an extra fact alongside the data, and update it on every change.

  • Max Stack. The same design, with >= instead of <=.
  • A queue with getMin. Harder, because items leave from the opposite end to where they enter. The answer is the monotonic deque from 4.6.6.
  • A stack with getSum. Each level stores the sum from the bottom up to it.

The general lesson: if a summary of the data must be available instantly, update it on every change instead of computing it when asked.

What the interviewer will push on ​

"Why <= and not <?" Give the push 2, push 2, pop example.

"Why can't one min variable work?" When you pop the minimum, nothing tells you what the previous minimum was. That one sentence explains the whole design.

"Can you save memory when the same minimum is pushed many times?" Store pairs of (value, count) in mins. Pushing the current minimum again just adds 1 to its count. Popping it subtracts 1, and only removes the pair when the count reaches 0.

"How would you make it safe for several threads at once?" Both stacks must change together. So every operation must hold one lock around both changes. If another thread could see the main stack updated but not mins, it would read a wrong minimum.

One thing to volunteer: offer the simpler always-push version first, because it cannot get <= wrong. Then offer the memory-saving version.

Next: 4.8.3 Evaluate Reverse Polish Notation. A stack used to calculate, rather than to remember.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet