Min Value from Stack

Question

I have a stack which contains some integer data. I want to find out the min value from Stack in O(1) time. Any idea?

PS: There is no ordering (increasing/decreasing) of data in Stack.

Thanks,

Naveen

Answer 1

Use two stacks. One is the data, one is the minimums. When you push onto the data stack, push the new minimum onto the minimums stack (the new minimum is the min of the item you're pushing and whatever is currently on the top of the minimums stack), and when you pop, pop off of both stacks (so that the two stacks always have the same number of elements). To find the minimum element, just look at the top of the minimums stack.

Pushing, popping and finding the min value are O(1).

Answer 2

O(n) is the best you're gonna do - you'd have to check each one of the values and compare them to the aggregator minimum, otherwise how would you know you got the lowest?

If you want, you can store the minimum as the values are added, making the pushes more expensive for the benefit of an O(1) read (of the pre-calculated minimum), but that's it.

Answer 3

A stack by definition is push/pop (LIFO) data structure. You can't using a single stack!