DSA · Stack · #120
Min Stack
Module 45 · difficulty 3/5·⏱ 30:00starts on first keystroke
Design a stack that supports `push`, `pop`, `top`, and retrieving the minimum element in **constant time**. Implement the `MinStack` class: - `MinStack()` initializes an empty stack. - `push(val)` pushes the integer `val` onto the stack. - `pop()` removes the element on the top of the stack. - `top()` returns the element on the top of the stack. - `getMin()` returns the minimum element currently in the stack. Each of `pop`, `top`, and `getMin` is always called on a non-empty stack. All four operations must run in **O(1)** time.
Examples
push(-2); push(0); push(-3); getMin(); pop(); top(); getMin();→getMin()=-3, top()=0, getMin()=-2— After popping -3, the minimum reverts to -2.push(5); push(5); getMin(); pop(); getMin();→getMin()=5, getMin()=5— Duplicate minimums must be tracked so popping one leaves the other.push(2); push(1); push(3); top(); getMin();→top()=3, getMin()=1
Constraints
- · -2^31 <= val <= 2^31 - 1
- · pop, top, and getMin operations are always called on non-empty stacks.
- · At most 3 * 10^4 calls total will be made to push, pop, top, and getMin.
- · Each operation must run in O(1) time.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.