easy

Min Stack

Build a stack that also reports its smallest value instantly, by storing a running minimum beside every pushed value.

1. Define the problem

Min Stack

Design a stack that also reports its smallest value at any moment, and does it in constant time. The stack supports four commands: push a value on top, pop the top value off, top to read the top value, and getMin to read the smallest value anywhere in the stack. The trick is to keep a second stack of minimums that grows and shrinks alongside the first one. Every time you push a value, you also push "the smallest value seen up to this point". When you pop, both stacks shrink together, so the minimum that was true earlier comes back automatically. To keep the tests simple, this version takes a list of commands and returns the answers produced by the top and getMin commands, in order.

Constraints

  • Each command is one of push, pop, top, getMin
  • push comes with one integer value
  • -105 ≤ value ≤ 105
  • pop, top and getMin are only used when the stack is not empty
  • At most 3 × 104 commands

Example

Inputoperations = [['push', -2], ['push', 0], ['push', -3], ['getMin'], ['pop'], ['top'], ['getMin']]
Output[-3, 0, -2]

Explanation getMin sees -3 while all three values are in the stack. After popping -3, the top is 0 and the smallest remaining value is -2.

2. Know the words first

In plain terms

Stack
A pile where you add and remove only at the top. The last item in is the first item out.
Constant time
The work does not grow with the size of the stack. Reading the minimum must be one quick lookup, not a scan of every value.
Minimum
The smallest number currently held in the stack.
3. Visualize the solution

Each cell shows one stacked value and the minimum recorded with it

Each cell shows one stacked value and the minimum recorded with it
Statusinit

The stack starts empty, with no values and no minimums.

What happens in this step

values = []
mins = []
output = []

Nothing has been pushed yet, so every slot shows a dash.
Step 1 of 8

Steps to visualize

  1. The row is the stack, bottom-left to top-right. A dash means an empty slot.
  2. Each cell reads value/min: the number pushed, then the smallest value in the stack at that moment.
  3. Pushing writes both numbers at once, so the minimum never has to be recalculated.
  4. Popping removes both numbers, which restores the minimum that was correct before that push.
  5. getMin reads the min half of the top cell, which is always the smallest value in the whole stack.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Each cell shows one stacked value and the minimum recorded with it
Statusinit

The stack starts empty, with no values and no minimums.

What happens in this step

values = []
mins = []
output = []

Nothing has been pushed yet, so every slot shows a dash.
Step 1 of 8
5. Solution

Solution

solution.tsTypeScript
function minStack(operations) {
  const values = [];
  const mins = [];
  const output = [];

  for (const op of operations) {
    const name = op[0];

    if (name === 'push') {
      const value = op[1];
      values.push(value);
      mins.push(mins.length === 0 ? value : Math.min(value, mins[mins.length - 1]));
    } else if (name === 'pop') {
      values.pop();
      mins.pop();
    } else if (name === 'top') {
      output.push(values[values.length - 1]);
    } else if (name === 'getMin') {
      output.push(mins[mins.length - 1]);
    }
  }

  return output;
}
Time
O(1) per command
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
operations = [['push', -2], ['push', 0], ['push', -3], ['getMin'], ['pop'], ['top'], ['getMin']][-3, 0, -2]example from the description
operations = [['push', 5], ['getMin'], ['top']][5, 5]one value is both the top and the minimum
operations = [['push', 1], ['push', 2], ['pop']][]no top or getMin command, so nothing is reported
operations = [['push', 2], ['push', 2], ['getMin'], ['pop'], ['getMin']][2, 2]the same value pushed twice stays the minimum after one pop
operations = [['push', 1], ['push', 3], ['push', 7], ['getMin'], ['top'], ['pop'], ['getMin']][1, 7, 1]the minimum sits at the bottom while the top keeps changing
operations = [['push', -1], ['push', -5], ['getMin'], ['pop'], ['getMin'], ['top']][-5, -1, -1]negative numbers and the minimum coming back after a pop

Keep reading