Min Max Stack Construction

Tags

Min Max Stack Construction

Category

Stacks

Difficulty

Medium

Problem Statement

Design a stack that supports the standard push, pop, and peek operations, along with retrieving the current minimum and maximum values in the stack, all in O(1) time.

Intuition

A regular stack gives us O(1) push, pop, and peek, but finding the min or max normally requires scanning all elements (O(n)). The key insight is that the min and max at any point in time depend only on the elements currently in the stack. By storing the min and max alongside each element when it is pushed, we always know the current min and max from the top of the stack. When an element is popped, the previous min and max are automatically restored from the element below.

Approach

  1. Use a main stack where each entry stores three values: {value, currentMin, currentMax}.
  2. Push(value):
    • If the stack is empty, push {value, value, value}.
    • Otherwise, compute newMin = min(value, top.currentMin) and newMax = max(value, top.currentMax), then push {value, newMin, newMax}.
  3. Pop(): Remove and return the top element's value.
  4. Peek(): Return the top element's value without removing it.
  5. GetMin(): Return top.currentMin.
  6. GetMax(): Return top.currentMax.

Pseudocode

class MinMaxStack:
    stack = []

    function push(value):
        if stack is empty:
            stack.push({value: value, min: value, max: value})
        else:
            newMin = min(value, stack.top().min)
            newMax = max(value, stack.top().max)
            stack.push({value: value, min: newMin, max: newMax})

    function pop():
        return stack.pop().value

    function peek():
        return stack.top().value

    function getMin():
        return stack.top().min

    function getMax():
        return stack.top().max

Time & Space Complexity

  • Time: O(1) for all five operations (push, pop, peek, getMin, getMax).
  • Space: O(n) where n is the number of elements in the stack. Each element stores three values instead of one, but this is still linear.

Key Insights

  • Storing cumulative min/max with each element is the critical technique. It trades a constant factor of space for O(1) retrieval.
  • When an element is popped, the min/max automatically revert to the correct values because the element below has its own stored min/max that reflects the state before the popped element was pushed.
  • An alternative approach uses two auxiliary stacks (one for mins, one for maxes), but the single-stack approach with tuples is simpler.

Edge Cases

  • Popping from an empty stack: should throw an error or return a sentinel value (depends on the specification).
  • Pushing duplicate values: the min/max stay the same, which is handled naturally.
  • Stack with one element: that element is both the min and the max.
  • All elements are the same: min and max are always that value.
  • Strictly increasing or decreasing sequence: only one of min or max changes with each push.

Linked mentions