Algorithm Description

Create a stack that supports an additional operation which can always return the minimum value present in the stack in constant time.

Considerations

This algorithm sounds pretty simple, but it can be a little trickier than it looks on the surface:

• You must have constant time access to the minimum value.
• Once the minimum value is popped, you must know the next smallest value.
• You must know how many times the minimum value exists in the stack so you don’t pop it prematurely.

A good way to address these considerations is to use two stacks; one to hold the real values, and one to hold the minimum values. The minimum value stack must record how many times the current minimum exists in the stack. So, if we push {5, 4, 3, 3, 4} to the real stack, then the min stack would hold {5, 4, 3, 3}. The last 4 does not need to be recorded as it has no effect on the current minimum. Both 3’s need to be recorded as 3 is still the minimum even if we pop the 1st 3.

Note that the implementation can be simplified by always re-adding the current minimum to the min-stack whenever a new element is added to the normal stack. This way, both stacks always have the same number of values, and we always do a push or a pop on both stacks at once. This simplification comes at a slight cost though. If we were unlucky, we may add a million elements to the stack, and the first one may be the minimum. At this point, our chosen implementation would only have 1 element in the min stack, while the simplified implementation would have a million elements in the min stack. This is a typical tradeoff with algorithms.

Sample Implementation

 import java.util.ArrayDeque;
 import java.util.Deque;

 //This class extends the ArrayDeque class in order to create a
 //generic minimum stack implementation. The underlying ArrayDeque
 //is used to hold all of the elements of the real stack, and a
 //secondary ArrayDeque is used in order to track the minimum
 //elements on that stack so that the minimum can be retrieved
 //in constant time.  Whenever a new element is pushed to the stack,
 //we check if it is less than or equal to the current minimum, and
 //if it is, we also push it to the min stack.  The reverse is done
 //when popping elements from the stack.  We need to push new
 //elements equal to the current minimum so that we can record the
 //fact that the current minimum exists multiple times in the stack.
 public class MinStack>
         extends ArrayDeque {

     //Secondary minimum stack to track the minimum element.
     private Deque minStack;

     //Allocate the minimum stack when the primary is created.
     public MinStack() {
         this.minStack = new ArrayDeque<>();
     }

     @Override
     public void push(E e) {
     //Add the new element to the min stack if it is less than or
     //equal to the min stack's top element.
     if (minStack.size() == 0 || e.compareTo(minStack.peek()) <= 0)
         minStack.push(e);

         //Add the element to the real underlying stack.
         super.push(e);
     }

     @Override
     public E pop() {

         //Get the top element from the real stack if there is one.
         if (super.size() == 0) return null;
         E item = super.pop();

         //If the element we popped off the real stack was the top
         //element of the min stack, also pop it of of the min stack.
         if (item != null && item.compareTo(
                 minStack.peek()) == 0) {
             minStack.pop();
         }

         //Return the popped item from the real stack.
         return item;
     }

     //Retrieve the minimum element off of the min stack in
     //constant time.
     public E min() {
         return minStack.peek();
     }

     public static void main(String[] args) {

     MinStack ms = new MinStack<>();
         ms.push(4); ms.push(5); ms.push(3); ms.push(3);
         ms.push(7); ms.push(2); ms.push(1); ms.push(2);
         ms.push(2); ms.push(1);

         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
         System.out.println("Minimum element = " + ms.min());
         System.out.println("Popping off: " + ms.pop());
     }
 }