Min stack

A stack that can also report its minimum value in O(1), using a second stack that tracks the running minimum.

The idea

Keep a second stack the same height as the first. Each time a value is pushed, also push the smaller of that value and the current minimum. The top of the min stack is always the minimum of everything still on the data stack, so GetMin is just a Peek.

Code

public class MinStack {
    readonly Stack<int> data = new();
    readonly Stack<int> mins = new();

    public void Push(int x) {
        data.Push(x);
        mins.Push(mins.Count == 0 ? x : Math.Min(x, mins.Peek()));
    }

    public void Pop() {
        data.Pop();
        mins.Pop();
    }

    public int Top() => data.Peek();

    public int GetMin() => mins.Peek();
}

Tips

• Pop both stacks together. The min stack is not touched independently, it only ever mirrors the data stack.
• This trick generalises: pair a stack with any running aggregate (min, max, sum) that needs O(1) access.

In the .NET library

A single stack of (value, minSoFar) pairs works just as well and uses the same O(n) space; two parallel stacks just keep the two concerns visually separate.