Interview question: Design a datastructure to support stack operations and to find minimun

Question

Design a data structure which has the following features

• push the data
• pops the last inserted data [LIFO]
• Gives the minimum

All of the above operations should have a complexity of O(1)

Answer 1

To do this, your data structure should contain two stacks. One should function as normal; the other one only contains the last minimum element seen. When you push an element, if it is less than /equal to the second stack's top (or the stack is empty), push it on the second stack as well. When you pop an element, if it is equal to the second stack's top, pop the second stack too.

The minimum at any time is the top of the second stack.

Answer 2

You can do this by maintaining two stacks

stack - do the usual push and pop operations on this stack.

minStack - this stack is used to get the min ele in the stack in O(1) time. At any point the top element of this stack will be the min of all the elements in the stack.

push( item a) 
    // push the element on the stack.
    stack.push(a)   

    // find the min of the ele to be pushed and the ele on top of minStack.
    if(minStack.isEmpty()) 
        min = a
    else
        min = Min(a,minStack.top())

    // push the min ele on the minStack.
    minStack.push(min) 
end push


pop()
    // pop and discard
    minStack.pop() 

    // pop and return
    return stack.pop() 
end pop


findMin()
    return minStack.top()
end findMin

In the above solution every time an element is pushed on stack, there is a corresponding push on minStack. So at any time the number of elements in stack and minStack are same. We can slightly optimize it by pushing an element onto minStack only if the element is smaller then the present min.

push( item a) 
    // push the element on the orginal stack.
    stack.push(a)   

    if(minStack.isEmpty())
            // if minStack is empty push.
            minStack.push(a) 
    // else push only if the element is less than or equal to the present min.
    else if(a <= minStack.top()) 
        minStack.push(a)
end push

pop()
    // pop from the stack
    ele = stack.top()     
    if(minStack.top() == ele)
            // pop only if the top element is ele.
        minStack.pop() 

    // return the popped element.
    return ele 
end pop

Answer 3

This question is actually asking for a Heap http://en.wikipedia.org/wiki/Heap_%28data_structure%29

PriorityQueue is a classical case (implementation of Heap). See java.util.PriorityQueue

I wish there was an easy way online to reference to Java language source code where I can see and refer to the implementation of PriorityQueue class.