Stack•Hard

Min Stack

Min Stack Design

To retrieve the minimum element in O(1) time, we use an auxiliary stack called the Min Stack. It mirrors operations and tracks the running minimum element at every state.

Push Algorithm

  1. Push value onto the Main Stack.
  2. If the Min Stack is empty, or the value is less than or equal to the current top of the Min Stack, push the value onto the Min Stack.

Pop Algorithm

  1. Retrieve value from top of the Main Stack.
  2. If this value is equal to the top of the Min Stack, pop it off the Min Stack too.
  3. Pop the value off the Main Stack.

Visualizing State

  Push(30)          Push(50)          Push(20)          Pop()
  Main   Min        Main   Min        Main   Min        Main   Min
  [30]   [30]       [50]   [30]       [20]   [20]       [50]   [30]
                    [30]              [50]   [30]       [30]
                                      [30]
  Min = 30          Min = 30          Min = 20          Min = 30