PPractick

The problem

A trading dashboard keeps a stack of recent price ticks. Traders can undo (pop) the latest tick, and the header must always show the lowest price currently on the stack, updated instantly. Scanning the stack for the minimum is O(n) per query. The fix is to remember, alongside each element, the minimum of the stack at the moment it was pushed. The minimum of the whole stack is then just the minimum stored with the top element, and popping automatically restores the previous minimum.

Example: push(-2), push(0), push(-3), getMin() → -3, pop(), top() → 0, getMin() → -2.

Function signature

class MinStack {
public:
    void push(int x);
    void pop();       // called only when non-empty
    int top();        // called only when non-empty
    int getMin();     // called only when non-empty
};

Test cases

Operations	Output	Explanation
push(-2) push(0) push(-3) getMin() pop() top() getMin()	-3 0 -2	LeetCode's example
push(5) push(3) push(7) getMin() pop() getMin() pop() getMin()	3 3 5
push(2) push(2) push(1) pop() getMin()	2	Duplicate minimums
push(INT_MIN) push(INT_MAX) getMin() top()	-2147483648 2147483647	Extreme values
push(1) top() getMin()	1 1

(Confirm: every operation must be O(1); pop, top and getMin are never called on an empty stack.)

How interviewers phrase it

• "Design a stack that supports push, pop, top, and retrieving the minimum element in constant time" (LeetCode 155).

Clarifying questions to ask

1. Must every operation be O(1)? (Yes.)
2. Can pop, top or getMin be called on an empty stack?
3. Is extra memory allowed, and how much? (O(n) is fine; O(1) extra is a follow-up.)

Follow-ups to expect

1. "Why not just keep one min variable?"
2. "How do pairs solve it?"
3. "Can you save space?"
4. "O(1) extra space?"
5. "Complexity?"

Related questions

• Trapping Rainwater Hard
• Largest rectangle in a histogram Hard
• Maximum Rectangles Hard
• Stock span problem Hard
• Celebrity Problem Hard
• LFU Cache Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in