Stack • Design Problems

Design a Min Stack

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

The Two Stack Approach

Use a `mainStack` to hold the actual elements, and an auxiliary `minStack` to keep track of the minimums. This avoids O(N) searching for the min.

Push Logic

Always push to the `mainStack`. Only push to the `minStack` if the new value is less than OR EQUAL to the current minimum (the top of the `minStack`).

Pop Logic

Always pop from the `mainStack`. If the value popped is exactly equal to the top of the `minStack`, pop from the `minStack` as well, because we just removed the current minimum.

Main Stack

Min Stack

Code Tracker

:::

1function push(val) {

2 mainStack.push(val);

3 if (minStack.length === 0 || val <= minStack[minStack.length - 1]) {

4 minStack.push(val);

5 }

6}

7function pop() {

8 let val = mainStack.pop();

9 if (val === minStack[minStack.length - 1]) {

10 minStack.pop();

11 }

12}

13function getMin() {

14 return minStack[minStack.length - 1];

15}