No. 02 - Stack with Function min()

Problem: Define a stack, in which we can get its minimum number with a function min. In this stack, the time complexity of min(), push() and pop() are all O(1).

Analysis: Our intuition for this problem might be that we sort all of numbers in the stack when we push a new one, and keep the minimum number on the top of stack. In this way we can get the minimum number in O(1) time. However, we cannot assure that the last number pushed in to container will be the first one to be popped out, so it is no longer a stack.

We may add a new member variable in a stack to keep the minimum number. When we push a new number which is less than the minimum number, we will update it. It sounds good. However, how to get the next minimum number when the current minimum one is popped? Fortunately, we have two solutions for this problem.

Solution 1: With Auxiliary Stack

It is not enough to have only a member variable to keep the minimum number. When the minimum one is popped, we need to get the next minimum one. Therefore, we need to store the next minimum number before push the current minimum one.

How about to store each minimum number (the less value of current minimum number and the number to be pushed) into an auxiliary stack? We may analyze the process to push and pop numbers via some examples (Table 1).

Step	Operation	Data Stack	Auxiliary Stack	Minimum
1	Push 3	3	3	3
2	Push 4	3, 4	3, 3	3
3	Push 2	3, 4, 2	3, 3, 2	2
4	Push 1	3, 4, 2, 1	3, 3, 2, 1	1
5	Pop	3, 4, 2	3, 3, 2	2
6	Pop	3, 4	3, 3	3
7	Push 0	3, 4, 0	3, 3, 0	0

Table 1: The status of data stack, auxiliary stack, minimum value when we push 3, 4, 2, 1, pop twice, and then push 0

At first we push 3 into both data stack and auxiliary stack. Secondly we push 4 into the data stack. We push 3 again into the auxiliary stack because 4 is greater than 3. Thirdly, we continue pushing 2 into the data stack. We update the minimum number as 2 and push it into the auxiliary stack since 2 is less the previous minimum number 3. It is same in the fourth step when we push 1. We also need to update the minimum number and push 1 into the auxiliary stack. We can notice that the top of auxiliary stack is always the minimum number if we push the minimum number into auxiliary stack in each step. 

Whenever we pop a number from data stack, we also pop a number from auxiliary stack. If the minimum number is popped, the next minimum number should be also on the top of auxiliary stack. In the fifth step we pop 1 from the data stack, and we also pop the number on the top of auxiliary (which is 1). We can see that the next minimum number 2 is now on the top of auxiliary stack. If we continue popping from both the data and auxiliary stacks, there are only two numbers 3 and 4 left in the data stack. The minimum number 3 is indeed on the top of the auxiliary stack. Therefore, it demonstrates that our solution is correct.

Now we can develop the required stack. The stack is declared as the following:

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

    std::stack<T>   m_min;      // auxiliary stack, to store minimum numbers

};

The function push, pop and min and top can be implemented as:

template <typename T> void StackWithMin<T>::push(const T& value)

{

    // push the new number into data stack

    m_data.push(value);

    // push the new number into auxiliary stack

    // if it is less than the previous minimum number,

    // otherwise push a replication of the minimum number

    if(m_min.size() == 0 || value < m_min.top())

        m_min.push(value);

    else

        m_min.push(m_min.top());

}

template <typename T> void StackWithMin<T>::pop()

{

    assert(m_data.size() > 0 && m_min.size() > 0);

    m_data.pop();

    m_min.pop();

}

template <typename T> const T& StackWithMin<T>::min() const

{

    assert(m_data.size() > 0 && m_min.size() > 0);

    return m_min.top();

}

template <typename T> T& StackWithMin<T>::top()

{

    return m_data.top();

}

The length of auxiliary stack should be n if we push n numbers into data stack. Therefore, we need O(n) auxiliary memory for this solution.

Solution 2: Without Auxiliary Stack

The second solution is trickier without an auxiliary stack. We do not always push numbers into data stack directly, but we have some tricky calculation before pushing.

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 is 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. Since 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 2*value-min. We should notice that 2*value-min should be 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.  

It sounds great. We feel confident to write code now with the correctness demonstration. The following is the sample code:

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;

}

In this solution, we don’t need the O(n) auxiliary stack, so it is more efficient in the perspective of memory utilization than the first solution above.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.