066. Design Min Stack

Bridge · Download this solution · All solutions and shared helpers

Problem

Implement MinStack with push(value), pop(), top() and get_min(). Each operation must take O(1) time. pop returns the removed integer; push returns None. Reading or popping an empty stack raises IndexError. Duplicate minima must work correctly.

Examples

Example 1

run_operations(MinStack, [("push",3),("push",1),("push",2),("get_min",),("pop",),("top",)])
=> [None, None, None, 1, 2, 1]

Removing two leaves the minimum and top equal to one.

Example 2

run_operations(MinStack, [])
=> []

An empty operation sequence returns no results.

Example 3

run_operations(MinStack, [("push",1),("push",1),("pop",),("get_min",)])
=> [None, None, 1, 1]

Popping one copy does not lose a duplicate minimum.

Reveal the worked solution and reasoning

Why this mechanism works

Store the minimum-so-far beside every pushed value. Then removing an entry restores the previous minimum automatically, including repeated minima. This uses extra state at each depth to make all operations independent of stack size.

State and boundaries

entries contains (value, minimum_through_this_depth) pairs. The final pair summarizes the whole current stack.

Protocol

On push combine value with the previous stored minimum.
Append both value and new minimum.
Pop one complete pair.
Read value or minimum from the final pair.

Visualization

push 3 -> (3,3)
push 1 -> (1,1)
push 2 -> (2,1)
pop 2 -> previous minimum still 1

Python implementation

from structures import run_operations

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

    def push(self, value):
        minimum = min(value, self.entries[-1][1]) if self.entries else value
        self.entries.append((value, minimum))

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

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

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

run_operations(MinStack, [("push",3),("push",1),("push",2),("get_min",),("pop",),("top",)])

L5 __init__: self.entries = []
self=MinStack{'entries':[]}

L8 push: minimum = min(value, self.entries[-1][1]) if self.entries else value
self=MinStack{'entries':[]}; value=3; minimum=3

L9 push: self.entries.append((value, minimum))
self=MinStack{'entries':[...]}; value=3; minimum=3

L8 push: minimum = min(value, self.entries[-1][1]) if self.entries else value
self=MinStack{'entries':[...]}; value=1; minimum=1

L9 push: self.entries.append((value, minimum))
self=MinStack{'entries':[..., ...]}; value=1; minimum=1

L8 push: minimum = min(value, self.entries[-1][1]) if self.entries else value
self=MinStack{'entries':[..., ...]}; value=2; minimum=1

L9 push: self.entries.append((value, minimum))
self=MinStack{'entries':[..., ..., ...]}; value=2; minimum=1

L18 get_min: return self.entries[-1][1]
self=MinStack{'entries':[..., ..., ...]}

L12 pop: return self.entries.pop()[0]
self=MinStack{'entries':[..., ...]}

L15 top: return self.entries[-1][0]
self=MinStack{'entries':[..., ...]}

Result: [None, None, None, 1, 2, 1]. Removing two leaves the minimum and top equal to one.

run_operations(MinStack, [])

L5 __init__: self.entries = []
self=MinStack{'entries':[]}

Result: []. An empty operation sequence returns no results.

Why the solution is correct

At depth one the value is its own minimum. Each later stored minimum is the smaller of the prior minimum and the incoming value. Popping removes only the final prefix summary, exposing the correct summary for the remaining prefix.

Time and space

O(1) time per operation and O(n) storage for n current values.

Common mistakes

A single global minimum cannot recover the previous minimum after a pop. Recording only strict new minima requires careful duplicate handling.

Reasoning card

State: entries contains (value, minimum_through_this_depth) pairs. The final pair summarizes the whole current stack.

Invariant: Current minimum is available at the top of auxiliary state.

Decision to rehearse: Store enough historical minimum state to survive pops.

Finish: Read value or minimum from the final pair

Transfer exercise

Store maximum-so-far alongside minimum-so-far and preserve constant-time operations.