Woodstock Blog

a tech blog for general algorithmic interview questions

[CC150v5] 3.2 Stack Min Value


How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element?

Push, pop and min should all operate in 0(1) time.


This is a very tricky question.

The key is how to use the minimum space to achieve O(1) query min operation. The trick is to count how many times the same min-value occur. Eg.

input: 5,3,3,1,1,2,2,2,2,2,2,2.

stack: 5,3,3,1,1.

So we can pop ‘1’ twice, pop ‘3’ twice, and pop ‘5’ once. Read the code!


public class StackMyAnswer extends Stack<Integer> {

    Stack<Integer> min = new Stack<Integer>();

    public void push(int value) {
        if (min.isEmpty() || value <= min.peek()) {

    public Integer pop() {
        int val = super.pop();
        if (!min.isEmpty() && val == min.peek()) {
        return val;

    public int min() {
        if (min.isEmpty()) {
            return Integer.MAX_VALUE;
        return min.peek();