O(1) getMin

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Solution

A separate minStack.

• push: push to stack as usual; if the new value is smaller or equal to the top of minStack, push to minStack
• pop: pop stack usual; if the top value of the stack is also the top value of minStack, pop minStack as well
• top: return stack top value
• getMin: return minStack top value

Key Points

Duplicates: make sure you push duplicated values to minStack, i.e. push to minStack if the new value is smaller or equal to the top of minStack, otherwise this example will fail:

push(1), push (1), pop(), pop()

x < getLast(minStack)

• push(1):
  • stack: [1]
  • minStack: [1]
• push (1):
  • stack: [1, 1]
  • minStack: [1]
• pop:
  • stack: [1]
  • minStack: []
• pop:
  • stack: []
  • minStack: IndexOutOfBoundsError

x <= getLast(minStack)

• push(1):
  • stack: [1]
  • minStack: [1]
• push (1):
  • stack: [1, 1]
  • minStack: [1, 1]
• pop:
  • stack: [1]
  • minStack: [1]
• pop:
  • stack: []
  • minStack: []