← all entries
A-022● Day 222026.05.27mediumleetcode #155neetcode150

Min Stack

#stack#design
↗ leetcode #155 · min-stack
01

Problem

· problem
P.022

Min Stack

↗ leetcode #155

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: - MinStack() initializes the stack object. - void push(int val) pushes the element val onto the stack. - void pop() removes the element on the top of the stack. - int top() gets the top element of the stack. - int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.

constraints
  • · -2³¹ ≤ val ≤ 2³¹ - 1
  • · pop(), top(), and getMin() are always called on non-empty stacks
  • · At most 3 × 10⁴ total calls to push, pop, top, and getMin
// paraphrased summary — see source for full text
examples
example 1input → output
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
[null, null, null, null, -3, null, 0, -2]
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Do all methods need to be O(1) time?
  • ☐
    Can we scan the entire stack in getMin()?
  • ☐
    When we push a value smaller than the current minimum, does it become the new minimum?
  • ☐
    Can we use a heap to track minimums?
  • ☐
    When we pop the minimum element, does the previous minimum automatically restore?
  • ☐
    Does getMin() need to remove an element?
  • ☐
    Can a single variable track all minimums?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize data structures
○
self.stack = []
○
self.stack = {}
○
self.min = float('inf')
step 2· Push: Add value to main stack│ nested
○
self.stack.append(val)
○
self.stack.insert(0, val)
step 3· Push: Calculate minimum at this level│ nested
○
val = min(val, self.minStack[-1] if self.minStack else val)
○
val = min(self.stack)
○
val = val
step 4· Push: Append minimum to auxiliary stack│ nested
○
self.minStack.append(val)
○
self.minStack.insert(0, val)
step 5· Pop: Remove from both stacks│ nested
○
self.stack.pop()
○
self.stack.pop()
step 6· Top: Return top element│ nested
○
return self.stack[-1]
○
return self.minStack[-1]
step 7· GetMin: Return minimum in O(1)│ nested
○
return self.minStack[-1]
○
return min(self.stack)
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class MinStack:
2
    def __init__(self):
3
        self.stack = []
4
        self.minStack = []
5
6
    def push(self, val: int) -> None:
7
        self.stack.append(val)
8
        val = min(val, self.minStack[-1] if self.minStack else val)
9
        self.minStack.append(val)
10
11
    def pop(self) -> None:
12
        self.stack.pop()
13
        self.minStack.pop()
14
15
    def top(self) -> int:
16
        return self.stack[-1]
17
18
    def getMin(self) -> int:
19
        return self.minStack[-1]
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
→
[null, null, null, null, -3, null, 0, -2]
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.