Woodstock Blog

a tech blog for general algorithmic interview questions

[Question] Min Stack



Implement a stack, enable O(1) Push, Pop Top, Min. Where Min() will return the value of minimum number in the stack.


Using two stacks.

The first one is the regular stack.

The second one only store minimum numbers.


Actual stack: (head) 16 15 29 19 18 (tail)

Auxiliary Stack: (head) 15 15 18 18 18 (tail)



Push(int x):
1) push x to the first stack (the stack with actual elements)
2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y.
…..a) If x is smaller than y then push x to the auxiliary stack.
…..b) If x is greater than y then push y to the auxiliary stack.

1) pop the top element from the auxiliary stack.
2) pop the top element from the actual stack and return it.

Code is skipped.