Design a stack which returns minimum element without using auxiliary stack

Design a stack to support an additional operation which returns the minimum element from the stack in constant time. The stack should continue supporting all other operations like push, pop, top, size, empty, etc, with no degrade in performance for these operations.


 

In previous approach we have used two stacks – the main stack to store the actual stack elements and an auxiliary stack to determine the minimum number in constant time. This implementation requires extra space for the auxiliary stack but this can be done without an auxiliary stack. The idea is to do some tricky calculation before pushing numbers into the stack.

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 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 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 stack direct without updating min. Therefore, when we find that the top of 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 stack (top) is less than the current min. Therefore, when we find that the top of stack is less then min, the real top (real pushed number value) is stored in min. After we pop the top of 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.

 
This is illustrated below in C++/Java:

C++

Download   Run Code

Output:

6
6
5
3
5
6

Java

Download   Run Code

Output:

6
6
5
3
5
6

 
Reference: Coding Interview Questions: No. 02 – Stack with Function min()

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of