Design a datastructure to support stack operations and to find minimum

Question

Interview 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

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