mafeshsho8lmafeshsho8l
Get Started
All coding questions

Min Stack

medium
Blind 75NeetCode 150stackdesign

Problem

Design a stack that supports push, pop, top, and retrieving the current minimum, with every operation running in constant time. The minimum must reflect only the values currently on the stack.

Examples

Input: push 5, push 3, getMin, pop, getMin
Output: 3 then 5
Min is 3 while 3 is present, then 5 after popping it.

Constraints

  • • At most 3 * 10^4 operations
  • • pop, top, getMin called only on a non-empty stack
Hints(tap to reveal)
  • 1. Keep a second stack of running minimums.
  • 2. Each entry can also store the min at the time it was pushed.
Optimal approach(spoiler)
  1. Back the structure with a main stack of values.
  2. Maintain a parallel stack holding the minimum seen up to each level.
  3. On push, record the smaller of the new value and the current min.
  4. On pop, discard the top of both stacks; getMin reads the min stack top.
  5. Every operation is O(1).

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor