Pages

Wednesday, June 19, 2013

Minimum Stack

Another common interview question is implementing a stack like data structure that besides supporting the traditional push() and pop() operations would provide a O(1) operation able to find the minimum element in the stack. The question is easy but I still decided to write it down because it seemed elegant to me.

So the solution consists in maintaining 2 stacks: one for performing the traditional operations as before, and another one that will always have the minimum on top for fast O(1) access. Imagine you have a set of numbers - 5, 2, 8, 5, 7, 13, 3, 11, 1, 6 and you start pushing them on the stack. Every time you push one number on the stack you compare it with the number on top of the other stack, and if it's smaller, you push it on the second stack too. This way after pushing all the numbers on both stacks you should have the second stack looking like this: 5, 2, 1 and the first stack looking as mentioned before like this 5, 2, 8, 5, 7, 13, 3, 11, 1, 6.

We also need to maintain the minimum when pop-ing elements from our new data structure. We pop from the first stack unconditionally, but from the second stack we check first if the element we just popped from the first stack is actually the element on top of the second stack; if so - we pop it from the second too.

This is how it would look if we pop all elements from the stack:

Iteration Stack 1 Stack 2 Current minimum
0 5, 2, 8, 5, 7, 13, 3, 11, 1, 6 5, 2, 1 1
1 5, 2, 8, 5, 7, 13, 3, 11, 1 5, 2, 1 1
2 5, 2, 8, 5, 7, 13, 3, 11 5, 2 2
3 5, 2, 8, 5, 7, 13, 3 5, 2 2
8 5, 2 5, 2 2
9 5 5 5
10

In code it looks very simple and short:

Note:
- It is not necessary to use 2 stacks here. Another way was making MinimumStack a child of Stack. I just like symmetry and encapsulation. Besides it seems easier to show the idea this way.

No comments:

Post a Comment