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.  

20 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. Hello Harry,

      A really interesting, clear and easily readable Stack with Function min() article of interesting and different perspectives. I will clap. So much is so well covered here.


      However, when. ebignore is present in your project directory, the EB CLI doesn't use git commands and semantics to create your source bundle. This means that EB CLI ignores files specified in. ebignore and includes all other files. In particular, it includes uncommitted source files.

      Encryption should be considered for sensitive data, as AWS S3 is a proprietary technology developed by Amazon themselves, and as yet unproven vis-a-vis a security standpoint.

      Anyways great write up, your efforts are much appreciated.

      Grazie,
      Kevin

      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
  12. Hey Brother,

    Seems like I won the lottery here….This is a treasure box of blogs and your folks are like leprechauns! Phenomenal read on No. 02 - Stack with Function min() AWS Training USA

    We have a t2.micro instance (built from amzn-ami-hvm-2016.09.1.20170119-x86_64-gp2) on which a customized WordPress is deployed. Following various posts here and elsewhere, various parameters for Apache and MySQL have been set to accommodate the 'size' of the host, including the deployment of a swap partition. The site has been running without issue for weeks.

    Please keep providing such valuable information.

    Shukran,
    Irene Hynes

    ReplyDelete
  13. Howdy Mate,


    This is indeed great! But I think perhaps you are generally referring No. 02 - Stack with Function min() which is getting unsustainable.


    I have a problem with cost allocation tags. I added a number of custom tags to my AWS resources. Activated the tags using activation GUI. I can see the tag keys as dimensions for Cost Explorer filters but no tag values are shown for filtering (only record "No TagKey"). More than a week passed since I added and activated the tags but nothing changes. Please advise. AWS Training





    Once again thanks for your tutorial.


    Merci Beaucoup,
    Ajeeth

    ReplyDelete