Saturday, September 10, 2011

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.  

17 comments:

  1. Thanks Harry sharing the question.
    I am not familiar with STL, just wonder stack.pop() means stack.peek()?

    ReplyDelete
    Replies
    1. The function stack.pop removes the element on the top. For for information, please refer to http://www.cplusplus.com/reference/stl/stack/pop/.

      Delete
  2. Another way(just one method, is not better than yours), I can implement this question by having each node value and "CURRENT" the minimum min together.

    class NewNode
    {
    public T value;
    public T min;
    }

    Just one thought, it is easy, but waste more memory.

    ReplyDelete
    Replies
    1. I like this solution against auxiliary stack but without auxiliary stack the solution given by Harry is awesome!

      Delete
  3. Harry I think your second solution wont stand good for all cases. Consider below

    Stack empty.
    1. Push 3
    stack=3 min_val = 3
    2. Push 4
    stack = 3,4 min_val = 3
    3. Push 2
    stack = 3,4,1(2*2 - 3 =1) min_val = 2
    4. Push 1
    stack = 3,4,0(2*1-2=0) min_val = 1.

    Now start poping
    1. 0< min_val(1)
    So 2*1 - 0 = 2
    But value to be popped is 1

    Even in you code while pushing you are updating value and pushing it but while popping you simply pop it out.

    ReplyDelete
    Replies
    1. when you say 2*1 = 2 , then the value to be popped is the multiplying factor ie 1 and the new value of min is the result ie 2 .. read the code again..

      Delete
    2. Hi Manikanda,
      We need to return m_min from POP(), if the control goes to below if block.
      if(m_data.top() < m_min)
      m_min = 2 * m_min - m_data.top();

      Harry mentioned same in TOP() but missed in POP().

      Delete
  4. This comment has been removed by the author.

    ReplyDelete
  5. what if i'm passing the value as INT_MIN? it would fail

    ReplyDelete
  6. The implimentation of stack using linkedlist is below :)

    Stack using Linked List>


    ... :-) .....

    ReplyDelete
  7. Can't we just compare the topmost element with the element that we are going to push into the stack, and this way we have to perform constant number of push and pop operations each time we push a new element to the top which will be minimum always.

    ReplyDelete
  8. What about overflow issue ?

    ReplyDelete
  9. Its simply superb.Feeling good to share the link to practice c# interview questions

    @ http://skillgun.com

    ReplyDelete
  10. Solution 2 without using the auxiliary stack is quite a different approach, I loved reading it.

    ReplyDelete
  11. What a wonderful post. I would like to say that this post is really very informational post. I really like it. how to do secondary data analysis

    ReplyDelete