Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Design a Min Stack

Stacksmedium

Course · Section 11: Working With Arrays · Lecture 149: Simple Array Methods

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time. Implement the `MinStack` class: - `push(val)` pushes `val` onto the stack. - `pop()` removes the element on top. - `top()` returns the top element. - `getMin()` returns the minimum element currently in the stack. All operations are called on a valid (non-empty where required) stack.

Examples

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: [-3, 0, -2]
getMin() is -3 after the three pushes. After pop() removes -3, top() is 0 and getMin() is -2.

Sample tests

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: [-3,0,-2]
Input: push(1), push(2), then getMin() and top()
Output: [1,2]

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Scanning the whole stack on getMin is O(n); the auxiliary min-stack keeps it O(1).
  • Forgetting to pop the min-stack alongside the main stack desynchronizes them.

Learning resources

  • Wikipedia: Stack
Approach & explanation (try first)

An auxiliary stack records the minimum so far at each depth. Pushing stores min(val, currentMin) and popping removes from both, so getMin is always the top of the min-stack in O(1).

Loading...
⌘/Ctrl + Enter

Run your code to see results.