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

Answer 2

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 3

This question is actually asking for a Heap

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.

Answer 4

There is a more creative solution without using an auxiliary stack.

Supposing that we are going to push a number value into a stack with minimum number min. If value is greater than or equal to the min, it is pushed directly into data stack. If it is less than min, we push 2**value* -min, and update min as value since a new minimum number is pushed.

How about to pop? We pop it directly if the top of data stack (it is denoted as top) is greater than or equal to min. Otherwise the number top is not the real pushed number. The real pushed number is stored as min. After the current minimum number is popped, we need to restore the previous minimum number, which is 2**min*-top.

Now let us demonstrate its correctness of this solution. When value is greater than or equal to min, it is pushed into data stack direct without updating min. Therefore, when we find that the top of data stack is greater than or equal to min, we can pop directly without updating min. However, if we find value is less then min, we push 2value*-min. We should notice that 2value*-min is less than value. Then we update current min as value. Therefore, the new top of data stack (top) is less than the current min. Therefore, when we find that the top of data stack is less then min, the real top (real pushed number value) is stored in min. After we pop the top of data stack, we have to restore the previous minimum number. Since top = 2**value*-previous min and value is current min, pervious min is 2*current min - top.

The C++ sample code is shown below:

template <typename T> class StackWithMin {
public:
    StackWithMin(void) {}
    virtual ~StackWithMin(void) {}

    T& top(void);
    void push(const T& value);
    void pop(void);
    const T& min(void) const;

private:
    std::stack<T>   m_data;     // data stack, to store numbers
    T               m_min;      // minimum number
};

template <typename T> void StackWithMin<T>::push(const T& value) {
    if(m_data.size() == 0) {
        m_data.push(value);
        m_min = value;
    }
    else if(value >= m_min) {
        m_data.push(value);
    }
    else {
        m_data.push(2 * value - m_min);
        m_min = value;
    }
}

template <typename T> void StackWithMin<T>::pop() {
    assert(m_data.size() > 0);

    if(m_data.top() < m_min)
        m_min = 2 * m_min - m_data.top();

    m_data.pop();
}

template <typename T> const T& StackWithMin<T>::min() const {
    assert(m_data.size() > 0);

    return m_min;
}

template <typename T> T& StackWithMin<T>::top() {
    T top = m_data.top();
    if(top < m_min)
        top = m_min;

    return top;
}

This solution is borrowed from my blog, and my book "Coding Interviews: Questions, Analysis & Solutions".