Min stack

Medium TimeO(1) per op SpaceO(n)

Build a stack that can push, pop, and also report the smallest value it currently holds — all three in constant time, so scanning for the minimum when asked does not count. Popping has to restore whatever the minimum was before the popped value arrived, and duplicate values are allowed, each accounted for separately.

Examples

Example 1

Input
demo()
Output
[2,5]
Push 5, 2, 7 and the smallest is 2; pop twice, only the 5 is left, and it is 5.

Example 2

Input
makeMinStack().getMin()
Output
undefined
A stack holding nothing has no smallest value to report.

The Code

function makeMinStack() {
  const values = [];
  const mins = [];
  return {
    push(v) {
      values.push(v);
      const currentMin = mins.length === 0 ? v : Math.min(v, mins[mins.length - 1]);
      mins.push(currentMin);
      return values.length;
    },
    pop() {
      mins.pop();
      return values.pop();
    },
    getMin() {
      return mins[mins.length - 1];
    }
  };
}
function demo() {
  const s = makeMinStack();
  s.push(5);
  s.push(2);
  s.push(7);
  const before = s.getMin();
  s.pop();
  s.pop();
  return [before, s.getMin()];
}
demo();
Done
Step through demo() call by call

More like this

All stacks & queues examples (8) →