Stack that Support Push, Pop, and GetMin in Constant Time

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?


Today, I read this interesting problem (exercise 4-44) from the excellent book “The Algorithm Design Manual” by Steven Skiena.

Initially I thought of using an extra min-heap to store the elements. Although this enables us to retrieve the minimum element in O(1), push and pop operations both operates in O(lg N), where N is the total number of elements in the stack. Definitely not a desirable method.

How about recording the current minimum in the stack? This works until you pop current minimum off the stack, where you would have to update your next minimum, which takes O(N) time to examine all elements.

Hint:
Assume you have an extra stack. What would you do with the extra stack?

Stack is a last in, first out (LIFO) data structure. It can be easily implemented either through an array or a linked list.

Solution:
The solution is surprisingly simple and elegant — Use an extra stack to maintain the minimums. What does this mean?

  • To retrieve the current minimum, just return the top element from minimum stack.
  • Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack too.
  • When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum stack too.

All of the above operates in O(1) constant time.

A Gotcha:

There is one small gotcha I purposely left in the above solution. Could you figure it out without looking at the code below first?

Further Thoughts:

Before we conclude this section, try a variation of this problem (appeared as a Google interview question):

Design a queue that supports push_rear, pop_front, and get_min in O(1). Would that be elegantly possible too?

Hint:
Use two queues.

If you need extra hints, see this post (both problems are related). If you could design a queue with push_rear, pop_front, and get_min in O(1), then finding the Sliding Window Maximum could be solved by direct application of such data structure.

VN:F [1.9.22_1171]
Rating: 4.4/5 (39 votes cast)
Stack that Support Push, Pop, and GetMin in Constant Time, 4.4 out of 5 based on 39 ratings

44 thoughts on “Stack that Support Push, Pop, and GetMin in Constant Time

  1. vitorbal

    If the value being pushed is equal to the current minimum, you push that value to the minimum stack as well. Is this the gotcha you were referring to?

    VA:F [1.9.22_1171]
    0
    1. Gautam

      Imagine a case where we push equal elements only in that case the Min stack will be exact copy of original stack, I think there is a way to optimize it.

      push to the minimum stack only when current element is lesser that Min.top().
      otherwise don’t push.

      pop() if S1.top() is equal to Min.top then pop from S1 and see if S1.top is still equal to Min.top if this is the case then don’t pop from Min stack otherwise pop from Min stack as well. This will further optimize the Min stack.

      Let me know if I am missing something.

      VN:F [1.9.22_1171]
      0
      1. Atul

        We however need to push the incoming element to the Min stack when it’s equal to the top element on Min stack.

        Consider the numbers 3, 1, 4, 1, 2.

        If the incoming number is 1(the second one) and we don’t push it onto the Min stack in the end the stacks will look like:
        Element stack: 3, 1, 4, 1, 2.
        Min stack: 3, 1

        Now when we pop twice – the second pop will pop 1 from the Min stack as well leading to incorrect return values for the subsequent calls to getMin()

        VA:F [1.9.22_1171]
        +3
  2. Anonymous

    can't validate if this was asked in an interview or not.. but what if u want the same operations push_rear, pop_front, get_min in a Queue in O(1) . Would that be elegantly possible.

    Here I was thinking of having a min-heap as an auxiliary structure for the get-min operation

    VA:F [1.9.22_1171]
    0
  3. 1337c0d3r

    @Anonymous:
    min-heap is not necessary and is slower. I've updated the above post with a "Further thoughts" section. Read it and see if you can figure it out.

    VA:F [1.9.22_1171]
    0
  4. 1337c0d3r

    @code spookz:
    Are you referring to the problem where stack that supports push, pop, and getMin in O(1)?
    If it is, I think you got the order wrong. 1 is pushed to the stack first, and therefore would be popped off last. After 1 is popped out, there would be no element left in the stack.

    VA:F [1.9.22_1171]
    0
  5. code spookz

    @1337c0d3r:
    input array : 1,2,3,4,5
    • To retrieve the current minimum, just return the top element from minimum stack.
    agreed
    • Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack too.
    since 1 is the min, there won' t be any other min other than 1, so 1 stays inside the min-stack (min stack has 1 in 1st iteration)
    • When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum stack too.
    agreed.. we have only 1 in min-stack so when we pop it out stack is empty!

    VA:F [1.9.22_1171]
    +1
  6. 1337c0d3r

    @code spookz:
    I don't see a problem there. When 1 is popped off (which will be the last element being popped off), you would pop off 1 from the minStack too. Since there are no elements left in the stack, the minStack should be empty too.

    VA:F [1.9.22_1171]
    0
  7. airfang

    I thought of a solution, seems to work, but I wouldn’t consider it elegant. Is it at least correct?

    Using two queues, std_queue and min_queue

    – push_rear:
    push onto std_queue, then if the element is smaller than the front of the min_queue, clear min_queue and then push the element onto min_queue. If the element is not smaller than the front of the min_queue, but it is smaller than the back of the std_queue, push onto min_queue. If at the same time the element is smaller than the back of the min_queue, store the front of the min_queue, clear min_queue, then push the prev_front of min_queue before pushing the element onto min_queue.

    – pop_front:
    pop from the std_queue, pop the min_queue if its front contains the same element, if min_queue is then empty (but the std_queue is not) push the front of the std_queue to min_queue. If now std_queue.front() is smaller than min_queue.front(), store the front of the min_queue, clear min_queue, push std_queue.front() and then the prev_front of min_queue to min_queue.
    This way we don’t have to push consecutive duplicates onto min_queue even if they satisfy the conditions, keeping min_queue.size() == 2.

    – get_min: return the front of the min_queue

    Note that the min_queue at most contains 2 elements, so clearing min_queue can also be considered constant (2 pops)

    VA:F [1.9.22_1171]
    0
  8. airfang

    Hey, now I revisited this problem today, based on your hints, I used a queue and a deque

    However, in this case the push operation would not be O(1) since it needs to clear up the min_queue. Any suggestions?

    VA:F [1.9.22_1171]
    +1
    1. xTristan

      this is amortized O(1), as if you consider all elements in the entire sequence, each of them only gets into each queue at most once.

      What you have is probably close enough to what 1337c0d3r suggests. I doubt there would be a consistent O(1) for PushRear. If yes, I would be very happy to learn.

      VA:F [1.9.22_1171]
      0
      1. caot

        oops

        while (!min_queue.empty() || elem < min_queue.back())

        change the above into

        if (!min_queue.empty() && elem < min_queue.back())

        VA:F [1.9.22_1171]
        0
  9. Mikhail

    I had come across this solution somewhere.It uses just one stack , and an extra variable and does all the operations in O(1). Please verify

    min = INT_MAX;//global

    push(key)
    {
    stack.push(key-min);
    if(key-min<0)
    {
    min = key; }

    }

    int pop(key)
    {
    temp = min;
    top = stack.pop();
    if(top<0)
    {
    min = key – top;
    return temp;
    }
    else
    return a[top]+min;
    }

    int getmin()
    {
    return min;
    }

    VA:F [1.9.22_1171]
    0
  10. Bala

    For stack operations:

    Push() and Pop() operations are anyway O(1) complexity.

    So, our aim to achieve getMin() in constant complexity i.e, O(1)….

    Have an extra variable(min) along with the value in each stack element which stores the min value of the current stack.So, getMin() is the value of stack’s top element extra variable(min) value, which is O(1) complexity.

    ==> Only one stack is used
    ==> It also addresses the gotcha pointed when redundant entries are present

    stack elements: 4 1 2 0 1
    ___________
    | value | min |
    ___________
    |__1__|__0__| <== getMin()
    |__0__|__0__|
    |__2__|__1__|
    |__1__|__1__|
    |__4__|__4__|

    VA:F [1.9.22_1171]
    +1
  11. Machine Learning

    I like most of the solution here but for this problem, I have some doubt that it is even possible. Since if you can do all the operations in O(1) time, then this would imply that you have a comparison sort algorithm that runs in O(n) time! This is not possible since (See CLR) it is known that comparison sort has a lower bound Omega(nlog n)!

    I think the problem here is that when an item gets push into the stack, at that moment it may not be a min item. But after sometime, it may sink deep in the original stack but becomes the smallest item (all the smaller items have been removed).

    VA:F [1.9.22_1171]
    0
  12. Amit

    #include
    #include
    #include
    #include

    using namespace std;

    queue main_queue;
    deque min_queue;

    void pushRear(int elem) {
    main_queue.push(elem);
    if(min_queue.empty())
    min_queue.push_back(elem);
    else{
    if(elem < min_queue.front())
    min_queue.push_front(elem);
    else
    min_queue.push_front(min_queue.front());
    }
    }

    void popFront() {
    int elem = main_queue.front();
    main_queue.pop();
    min_queue.pop_front();
    }

    int getMin()
    {
    return min_queue.front();
    }

    int main()
    {
    pushRear(4);
    pushRear(1);
    pushRear(2);
    pushRear(0);
    pushRear(1);
    popFront();
    popFront();
    printf("Min : %d\n",getMin());
    return 0;
    }

    Is this correct?

    VA:F [1.9.22_1171]
    0
  13. Yunzhao

    Hi,

    I am not sure there is an issue there?

    Since not every item has been pushed into the minStack, the min of the stack ‘elements’ can’t be obtained via getMin() any more when the stack ‘minStack’ is empty.

    VA:F [1.9.22_1171]
    0
  14. Pingback: Amazon interview preparation | What I learn, I blog !

  15. Moussa

    @1337c0d3r: do u have a reference for the “two-queue” solution to the Further Thoughts? I can not figure out how to maintain minGet() in O(1) with two queues.

    VA:F [1.9.22_1171]
    0
  16. Pingback: Epic List of Interview Questions | kate{mats}

  17. Sagar

    Can anyone point out what’s wrong with Bala’s solution? That seems to be the most trivial of the lot and avoids any of the extra data structures.

    VA:F [1.9.22_1171]
    0
    1. Pat O'Brien

      Bala’s solution is fine, but it is equivalent to using two stacks, and the code is going to be more awkward because of storing a structure (value, min) at each element in the stack.

      For a stack of values that would be size N, Bala’s stack will require 2N, so that is one drawback. Also, for a solution that would require min and max, Bala’s solution, as it stands, would require 3N.

      In addition, the code will be more awkward when managing the structured element, rather than having simple integer values in the case of using two separate stacks, as in the original solution.

      Mikhail made an interesting suggestion here (http://leetcode.com/2010/11/stack-that-supports-push-pop-and-getmin.html#comment-1159) for an even more efficient solution, but his code (or psuedocode) isn’t complete. The idea, nonetheless, is a good one, and an example of that type of solution – which is based more on mathematics – is on Stack Overflow with the title: “design a stack such that getMinimum should be O(1)” and the URL (not sure that will work here: http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1.)

      One drawback with the SO solution is that, as it stands, it works *only* for getMinimum or *only* for getMaximum, but not for both at the same time.

      All in all, an interesting problem with an interesting set of solutions.

      VN:F [1.9.22_1171]
      0
  18. Ven

    Total blunder. This solution is not gonna work. At some point the minStack is gonna run out of accurate minimum.

    Take an example:
    Insert 6, 5, 2, 8, 10, 1 in the same order
    elementStack -> 6, 5, 2, 8, 10, 1
    minStack -> 6, 5, 8, 10, 2, 1

    minStack.top() -> 1 –> correct

    After 1st delete:
    elementStack – 6, 5, 2, 8, 10
    minStack – 6, 5, 8, 10, 2
    getmin -> minStack.top() -> 2 –> correct

    After 2nd delete:
    elementStack – 6, 5, 2, 8
    minStack – 6, 5, 8, 10, 2
    getmin -> minStack.top() -> 2 –> correct

    After 3rd delete:
    elementStack – 6, 5, 2
    minStack – 6, 5, 8, 10, 2
    getmin -> minStack.top() -> 2 –> correct

    After 4th delete:
    elementStack – 6, 5
    minStack – 6, 5, 8, 10
    getmin -> minStack.top() -> 10 –> incorrect

    VA:F [1.9.22_1171]
    0
    1. Amit

      I think your min stack is wrong. It should be

      Take an example:
      Insert 6, 5, 2, 8, 10, 1 in the same order
      elementStack -> 6, 5, 2, 8, 10, 1
      minStack -> 6, 5, 5, 5, 2, 1

      VA:F [1.9.22_1171]
      0
  19. Pingback: LeetCode | Technical interview solutions

  20. Pingback: LeetCode Min Stack: Optimal Memory Implementation | Sigmainfy 烟客旅人

  21. Wangxinyan


    class MinStack {

    class Stack{
    final int siteNum = 50;
    int []arr = new int[siteNum];
    int []min = new int[siteNum];
    int top = -1;
    }

    private Stack s = new Stack();

    public void push(int x)
    {
    s.arr[++s.top] = x;
    if(s.min[s.top] > x)
    {
    s.min[++s.top] = x;
    }
    }

    public int pop()
    {
    if(s.top == -1)
    {
    System.out.print("The stack is empty!");
    return 0;
    }
    else
    {
    if(s.arr[s.top] == s.min[s.top])
    {
    int x = s.min[s.top--];
    }
    }
    int y = s.arr[s.top--];
    return y;
    }

    public int top() {

    return(s.arr[s.top]);

    }

    public int getMin()
    {
    return (s.min[s.top]);
    }

    }

    why it tells me runtime rrror?

    VN:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*