Stack with Minimum

Stack with Minimum

Problem

You need to implement a stack that supports three operations:

• push(x) — add an element to the end
• pop() — remove an element from the end
• get_min() — get the minimum element

All operations must run in O(1).

Idea

A regular stack cannot quickly find the minimum — to do that, you would have to traverse all elements every time.

Solution:

We will store two stacks:

1. st — a regular stack
2. mn — a stack of minimums

In the mn stack we will push the current minimum at each step.

How it works

On push(x):

• add x to the main stack
• to the minimums stack add:
  • x if the stack is empty
  • min(x, current minimum) otherwise

On pop():

• remove an element from both stacks

On get_min():

• return the top of the minimums stack

Implementation (C++)