Min stack

An ordinary stack already owns push, pop, and top. The missing operation is restoring the correct minimum after a pop.

State augmentation

Store each value beside the minimum of the complete stack prefix ending there:

entry = (value, min(value, previous_prefix_minimum))

Then:

• get_min() reads the second field of the top entry;
• pop() automatically reveals the previous prefix minimum.

Invariant: the saved minimum in entry i equals the minimum of values 0 .. i.

flowchart LR
  accTitle: Min stack stores the minimum with every prefix
  accDescr: Entries pair each pushed value with the minimum through that position. Popping the top value two automatically reveals the previous minimum three.
  A["bottom<br/>(value 3, min 3)"] --> B["(value 5, min 3)"]
  B --> C["top<br/>(value 2, min 2)"]
  C -->|"pop 2"| D["new top<br/>(value 5, min 3)"]
  D --> E["get_min returns 3<br/>no rescan needed"]

The second field is a cached answer for that exact prefix. A pop restores an older prefix and therefore restores its answer in the same operation.

Tested templates

PythonC++17C++11

class MinStack:
    """Store each value beside the minimum for its complete prefix."""

    def __init__(self) -> None:
        self.entries: list[tuple[int, int]] = []

    def push(self, value: int) -> None:
        current_minimum = value if not self.entries else min(value, self.entries[-1][1])
        # The saved prefix minimum restores automatically after a pop.
        self.entries.append((value, current_minimum))

    def pop(self) -> int:
        if not self.entries:
            raise IndexError("pop from empty MinStack")
        return self.entries.pop()[0]

    def top(self) -> int:
        if not self.entries:
            raise IndexError("top from empty MinStack")
        return self.entries[-1][0]

    def get_min(self) -> int:
        if not self.entries:
            raise IndexError("minimum of empty MinStack")
        return self.entries[-1][1]

class MinStack {
 public:
  void push(int value) {
    const int current_minimum =
        entries_.empty() ? value : std::min(value, entries_.back().second);
    // The saved prefix minimum restores automatically after a pop.
    entries_.push_back({value, current_minimum});
  }

  int pop() {
    require_entry("pop from empty MinStack");
    const int value = entries_.back().first;
    entries_.pop_back();
    return value;
  }

  int top() const {
    require_entry("top from empty MinStack");
    return entries_.back().first;
  }

  int get_min() const {
    require_entry("minimum of empty MinStack");
    return entries_.back().second;
  }

 private:
  void require_entry(const char* message) const {
    if (entries_.empty()) {
      throw std::logic_error(message);
    }
  }

  std::vector<std::pair<int, int>> entries_;
};

class MinStack {
 public:
  void push(int value) {
    const int current_minimum =
        entries_.empty() ? value : std::min(value, entries_.back().second);
    // The saved prefix minimum restores automatically after a pop.
    entries_.push_back({value, current_minimum});
  }

  int pop() {
    require_entry("pop from empty MinStack");
    const int value = entries_.back().first;
    entries_.pop_back();
    return value;
  }

  int top() const {
    require_entry("top from empty MinStack");
    return entries_.back().first;
  }

  int get_min() const {
    require_entry("minimum of empty MinStack");
    return entries_.back().second;
  }

 private:
  void require_entry(const char* message) const {
    if (entries_.empty()) {
      throw std::logic_error(message);
    }
  }

  std::vector<std::pair<int, int>> entries_;
};

Alternative two-stack design

Keep one value stack and one minimum stack. Push into the minimum stack when the new value is ≤ its top, and pop from it when the removed value equals its top. The ≤ is necessary to preserve duplicate minima.

Complexity and tests

• Every operation: O(1).
• Space: O(n).
• Test duplicate minima, removing the current minimum, negative values, and empty operations.

Practice

LeetCode: Min Stack