Minimum Maximum Stack

Problem : Design a stack of Numbers which will give you the minimum and maximum of all the elements it contains.

This problem is also known as MinStack or MaxStack problem which expects you to find only the minimum or maximum. It is restated here to capture both. A stack typically has push(), pop() and size() operations. In order to find the minimum and the maximum, we will need to iterate over the elements of the stack each time we want to find the minimum and maximum. This will result in O (n) time complexity. And typically stack does not let us iterate over the elements. Many do not know that the java.util.Stack implementation does allow it as it extends java.util.Vector.

We can make it more efficient by storing the minimum and maximum as instance variables in our stack and update them when ever we push a new number on to the stack. This will result in O(1) complexity for updating the max and min when pushing new numbers on stack, but when we pop the number which is currently set as the maximum or minimum, we need to iterate and find the max and min again. This would result in O(n) complexity again.

We can make it more efficient by using a helper data structure like a SortedSet which ensures O (log n) complexity for adding, deleting and contains operations. Since the numbers being pushed on to the stack will be sorted in the sorted set, we can get the maximum and minimum in O (1). Here is the code for this -

package org.blogkoder.algorithms.stack;

import java.util.SortedSet;
import java.util.TreeSet;
import java.util.Stack;

/**
* User: blogkoder
* Copyright : blogkoder
*/

/**
* This is an implementation of a numbers stack which also
* gives the minimum and maximum of the numbers.
*/
public class MinMaxStack<Number>
{
  private SortedSet<Number> sortedSet = new TreeSet<Number>();

  private Stack<Number> stack = new Stack<Number>();

  /**
   * This pushes the number on to the stack.
   *
   * SortedSet ensures insertion at O (log n)
   *
   * @param number
   */
  public void push(Number number)
  {
      stack.push(number);

      sortedSet.add(number);
  }

  /**
   * This pops the number off the stack.
   *
   * SortedSet ensures removal at O (log n)
   *
   * @return Number
   * @exception java.util.EmptyStackException  if this stack is empty.
   */
  public Number pop()
  {
      Number number = stack.pop();
      sortedSet.remove(number);

      return number;
  }

  /**
   * Returns the maximum at constant time O (1).
   *
   * @return Number - maximum of the elements in the stack.
   *
   * @exception java.util.NoSuchElementException - if the stack is empty.
   */
  public Number maximum()
  {
      return sortedSet.last();
  }

  /**
   * Returns the maximum at constant time O (1).
   *
   * @return Number - minimum of the elements in the stack.
   *
   * @exception java.util.NoSuchElementException - if the stack is empty.
   */
  public Number minimum()
  {
      return sortedSet.first();
  }
}

But this will not handle duplicate values. Since we are using a Set, it does not allow duplicate values. So if we push duplicate numbers on the stack and pop one of them, then the maximum/minimum will not return the right value. The fix for this is to wrap the Number with a unique id and override the equals method of the wrapper. I leave this to you.