Notes
All notes

Min Stack: the minimum so far

Problem. Design a stack that supports push, pop, top and getMin — and getMin must return the smallest element currently in the stack, all in O(1) time.

push(-2)   push(0)   push(-3)   getMin() -> -3   pop()   top() -> 0

Every operation except getMin is what a stack already does. The whole problem is making the minimum a constant-time read instead of a scan.

The obvious idea is too slow

A stack gives you the top for free. The minimum is somewhere in the middle, so the naive getMin walks the whole stack and takes \(O(n)\) — and each pop can destroy the answer, so caching a single min value does not work either:

The fix is to store the history of minimums, not just the latest one.

The idea: a second stack of running minimums

Keep two stacks:

When you push a new value it becomes the new minimum only if it is less than or equal to the old minimum; otherwise the old minimum is still the smallest, so mins does not change. When you pop a value that was the minimum, the entry below it on mins is precisely the minimum that existed before it — so the old minimum is restored automatically.

The invariant

At every moment, mins[-1] == min(stack), and mins is non-increasing from bottom to top.

The three rules that maintain it:

The <= in push is the subtle part — it is what makes duplicates work, and we will see exactly why below.

Dry run

Start empty and push 5, 3, 3, 7.

After push(5). Both stacks hold a single 5; the top of mins is the minimum so far.

\begin{tikzpicture}[
  b/.style={draw,thick,minimum width=1.25cm,minimum height=0.68cm,font=\large},
  mn/.style={b,fill=green!35},
  pu/.style={b,fill=orange!35},
  hd/.style={font=\small\ttfamily,text=black!70}
]
  \node[hd] at (0,1.2) {stack};
  \node[hd] at (2.1,1.2) {min};
  \node[b] at (0,0.4) {5};
  \node[mn] at (2.1,0.4) {5};
\end{tikzpicture}

After push(3), push(3), push(7). The first 3 is smaller than 5, so it goes on mins. The second 3 is equal to the current minimum, so it also goes on mins (this is the <=). The 7 is larger than the minimum, so it only goes on the main stack. The green box is the current minimum: 3.

\begin{tikzpicture}[
  b/.style={draw,thick,minimum width=1.25cm,minimum height=0.68cm,font=\large},
  mn/.style={b,fill=green!35},
  pu/.style={b,fill=orange!35},
  hd/.style={font=\small\ttfamily,text=black!70}
]
  \node[hd] at (0,3.35) {stack};
  \node[hd] at (2.1,3.35) {min};
  \node[b] at (0,0.4) {5};
  \node[b] at (0,1.12) {3};
  \node[b] at (0,1.84) {3};
  \node[pu] at (0,2.56) {7};
  \node[b] at (2.1,0.4) {5};
  \node[b] at (2.1,1.12) {3};
  \node[mn] at (2.1,1.84) {3};
\end{tikzpicture}

In table form, the whole trace reads:

push(5)    stack=[5]        min=[5]
push(3)    stack=[5,3]      min=[5,3]
push(3)    stack=[5,3,3]    min=[5,3,3]
push(7)    stack=[5,3,3,7]  min=[5,3,3]
getMin()   -> 3

pop() removes 7. The popped value is 7, which is not mins[-1] (3), so mins is untouched. The minimum is still 3.

\begin{tikzpicture}[
  b/.style={draw,thick,minimum width=1.25cm,minimum height=0.68cm,font=\large},
  mn/.style={b,fill=green!35},
  hd/.style={font=\small\ttfamily,text=black!70}
]
  \node[hd] at (0,2.6) {stack};
  \node[hd] at (2.1,2.6) {min};
  \node[b] at (0,0.4) {5};
  \node[b] at (0,1.12) {3};
  \node[b] at (0,1.84) {3};
  \node[b] at (2.1,0.4) {5};
  \node[b] at (2.1,1.12) {3};
  \node[mn] at (2.1,1.84) {3};
\end{tikzpicture}

pop() again. This time the popped value is 3, which equals mins[-1], so mins pops as well. But a 3 still sits underneath, so the minimum is still 3 — this is exactly why we pushed the duplicate in the first place.

\begin{tikzpicture}[
  b/.style={draw,thick,minimum width=1.25cm,minimum height=0.68cm,font=\large},
  mn/.style={b,fill=green!35},
  hd/.style={font=\small\ttfamily,text=black!70}
]
  \node[hd] at (0,1.9) {stack};
  \node[hd] at (2.1,1.9) {min};
  \node[b] at (0,0.4) {5};
  \node[b] at (0,1.12) {3};
  \node[b] at (2.1,0.4) {5};
  \node[mn] at (2.1,1.12) {3};
\end{tikzpicture}

One more pop(). Now the last 3 leaves both stacks, and the minimum falls back to the 5 that was recorded below it.

\begin{tikzpicture}[
  b/.style={draw,thick,minimum width=1.25cm,minimum height=0.68cm,font=\large},
  mn/.style={b,fill=green!35},
  hd/.style={font=\small\ttfamily,text=black!70}
]
  \node[hd] at (0,1.2) {stack};
  \node[hd] at (2.1,1.2) {min};
  \node[b] at (0,0.4) {5};
  \node[mn] at (2.1,0.4) {5};
\end{tikzpicture}

At no point did we scan anything: getMin read the top of mins, and each push or pop touched at most one box on each stack.

Why <= and not <

Suppose push only recorded a new minimum when the value was strictly smaller. Then the second 3 would be skipped, leaving min = [5, 3] while stack = [5, 3, 3]. Popping one 3 would pop the 3 off mins too, and the reported minimum would jump to 5 even though a 3 is still on the stack:

\begin{tikzpicture}[
  b/.style={draw,thick,minimum width=1.25cm,minimum height=0.68cm,font=\large},
  wrong/.style={b,fill=red!30},
  hd/.style={font=\small\ttfamily,text=black!70},
  note/.style={font=\small,text=red!70!black}
]
  \node[hd] at (0,1.9) {stack};
  \node[hd] at (2.1,1.9) {min};
  \node[b] at (0,0.4) {5};
  \node[b] at (0,1.12) {3};
  \node[wrong] at (2.1,0.4) {5};
  \node[note,anchor=west] at (3.0,0.75) {getMin() says 5,};
  \node[note,anchor=west] at (3.0,0.35) {but a 3 is still present};
\end{tikzpicture}

With <=, duplicates are pushed onto mins and the invariant survives.

The code

class MinStack:
    def __init__(self):
        self.stack = []   # the elements
        self.mins = []    # non-increasing stack of running minimums

    def push(self, val):
        self.stack.append(val)
        if not self.mins or val <= self.mins[-1]:
            self.mins.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.mins[-1]:
            self.mins.pop()
        return val

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

    def getMin(self):
        return self.mins[-1]

The same design in Go:

type MinStack struct {
	stack []int
	mins  []int
}

func (s *MinStack) Push(val int) {
	s.stack = append(s.stack, val)
	if len(s.mins) == 0 || val <= s.mins[len(s.mins)-1] {
		s.mins = append(s.mins, val)
	}
}

func (s *MinStack) Pop() int {
	val := s.stack[len(s.stack)-1]
	s.stack = s.stack[:len(s.stack)-1]
	if val == s.mins[len(s.mins)-1] {
		s.mins = s.mins[:len(s.mins)-1]
	}
	return val
}

func (s *MinStack) Top() int    { return s.stack[len(s.stack)-1] }
func (s *MinStack) GetMin() int { return s.mins[len(s.mins)-1] }

One stack instead of two

You can fold the two stacks together by storing the running minimum inside each entry. Push the pair (value, min_so_far); the top of stack carries the answer, so no second array is needed:

class MinStack:
    def __init__(self):
        self.stack = []          # (value, minimum of everything up to here)

    def push(self, val):
        cur = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, cur))

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

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

    def getMin(self):
        return self.stack[-1][1]

This is the same idea with the two stacks zipped into one row per element — the min field is the mins stack growing in lockstep.

Complexity

Operation Time Space
push \(O(1)\) \(O(1)\) amortised
pop \(O(1)\) \(O(1)\)
top \(O(1)\) \(O(1)\)
getMin \(O(1)\) \(O(1)\)

Across a sequence of \(n\) operations the total space is \(O(n)\): in the worst case (values pushed in decreasing order) mins grows as fast as stack.

Edge cases