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?

**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?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
struct StackGetMin { void push(int x) { elements.push(x); if (minStack.empty() || x <= minStack.top()) minStack.push(x); } bool pop() { if (elements.empty()) return false; if (elements.top() == minStack.top()) minStack.pop(); elements.pop(); return true; } bool getMin(int &min) { if (minStack.empty()) { return false; } else { min = minStack.top(); return true; } } stack<int> elements; stack<int> minStack; }; |

**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.

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?

0Yes, this is the gotcha I'm referring to. This is due to pushing duplicate elements onto the stack.

+1Imagine 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.

0We 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()

+3I had this problem on the midterm given by Skiena. xD

0does this work for the next min item after it's been popped?

0Nevermind, it's elegant. Worked it out on paper.

0can'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

0@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.

0not convinced 🙁

1,2,3,4,5

only 1 goes to the min stack

after 1 is popped out.. getMin won't work

+5@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.

0@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!

+1note that the getMin() uses top(), not pop(). So getMin() does not remove any elements from the minStack.

+1@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.

0@1337c0d3r:

thank you previously I got the problem wrongly..

0I 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)

0Hey, 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?

+1this is

amortizedO(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.

0Agree. The 2queue method 1337c0d3r suggests gotta have an amortized O(1) pushRear, good enough though.

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

change the above while to if

0oops

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

change the above into

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

0I 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;

}

0For 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__|

+1This was my first thought as well. Isn’t this the best solution? Or did you find anything else?

0I 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).

0it only maintains a current min, not sorting the whole sequence.

-2#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?

0The output of Min: is 1 with the following operation.

pushRear(4);

pushRear(1);

pushRear(2);

pushRear(0);

pushRear(1);

popFront();

popFront();

The min shall be zero, isn’t it?

0Hi,

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.

0How does this code work? For the input 3,6,1,2, it returns 2 when pop() is done.

0Pingback: Amazon interview preparation | What I learn, I blog !

@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.

0@1337c0d3r, to implement the O(1) queue operation with O(1) min(), you suggested using two queues. Are you intend to suggest using two stacks?

If we use two stacks, we can use the special stack you designed here, and implement the queue operation.

http://stackoverflow.com/questions/4802038/implement-a-queue-in-which-push-rear-pop-front-and-get-min-are-all-consta

0Pingback: Epic List of Interview Questions | kate{mats}

For the queue case in furthur thoughts, how do you use 2 queues? I think 1 element queue and 1 minstack will solve the problem

0I think the solution for a queue like this needs a regular queue and a deque. Do you think a second queue is enough?

0Can 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.

0Bala’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.

0Total 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

0I 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

0Sorry

Insert 6, 5, 2, 8, 10, 1 in the same order

elementStack -> 6, 5, 2, 8, 10, 1

minStack -> 6, 5, 2, 2, 2, 1

0Pingback: LeetCode | Technical interview solutions

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

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?`

0