Stack Min

Design a stack which, in addition to push and pop, has a function which returns the minimum element? Push, pop and min should all operate in \(O(1)\) time.

Solutions

At first glance, a simple solution appears to be adding an intribute attribute to the Stack class which keeps track of the minimum value in the stack. However, this solution will not operate in \(O(1)\) time. When the minimum element is removed from the stack, the class will need to perform a search to find the new minimum element, and the search will take \(O(n)\) time.

A different solution involves adding an attribute to the Node class, which keeps track of the minimum element below that node in the stack. When a new node is added to the stack, this attribute can be calculated by comparing the min of the previous top of the stack against the value of the added element.

class StackNode:
  def __init__(self, value):
    self.value = value
    self.min = None
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

  def push(self, value):
    if(self.top == None):
      node = StackNode(value)
      node.min = value
      self.top = node

    else:
      node = StackNode(value)
      node.min = min(value, self.top.min)
      node.next = self.top
      self.top = node

  def pop(self):
    value = self.top.value
    self.top = self.top.next
    return value

  def min(self):
    return self.top.min

One disadvantage to this approach is the extra space required to store the minimum at each node. A solution which requires less space involves creating two stacks, one to keep track of the values, and another to keep track of the minima. When a value is removed from the stack, if the value is the same as the top of the minima stack, we can pop off the top element of both stacks to reveal the new minimum.

class Node:
  def __init__(self, value):
    self.value = value
    self.next = None

class StackWithMin:
  def __init__(self):
    self.minimum = None
    self.top = None

  def push(self, value):
    if(self.minimum):
      if(value < self.minimum.value):
        node = Node(value)
        node.next = self.minimum
        self.minimum = node

      n = Node(value)
      n.next = self.top
      self.top = n
    else:
      node = Node(value)
      self.minimum = node

      n = Node(value)
      self.top = n

  def pop(self):
    value = self.top
    self.top = self.top.next

    if(value == self.minimum.value):
      self.minimum = self.minimum.next

    return value

  def min(self):
    return self.minimum.value