Min Max Stack
Prompt
Implement a MinMaxStack class that works like a regular stack but also lets you retrieve the current minimum and maximum values at any time, without removing anything.
Your class should support:
push(number)— adds a number to the toppop()— removes and returns the top numberpeek()— returns the top number without removing itisEmpty()— returnstrueif the stack is emptygetMin()— returns the smallest number currently in the stackgetMax()— returns the largest number currently in the stack
getMin() and getMax() must work in constant time (no looping through the whole stack).
Playground
You already know how to build a basic stack. The challenge
is making getMin() and getMax() fast. If you loop
through the whole stack every time, that's O(n). Can you
store the min/max information alongside each element so
you can look it up instantly?
Keep a second stack that runs in parallel with the main stack. Every time you push a number, also push an object like { min: ..., max: ... } onto the second stack. The min is the smaller of the new number and the previous min. The max is the larger of the new number and the previous max. When you pop, pop from both stacks.
Solution
Explanation
If you've already solved the basic Stack question, you know how push, pop, peek, and isEmpty work. This question adds a twist: you also need getMin() and getMax(), and they need to be fast.
The naive approach (and why it's slow)
The obvious way to find the minimum is to loop through the entire stack every time someone calls getMin(). That works, but it's O(n) for every call. If the stack has 10,000 elements, you're scanning all 10,000 every time. Interviewers expect O(1).
The trick: a parallel stack
The key insight is to maintain a second stack that mirrors the main stack, but instead of storing the actual values, it stores the current min and max at that point in time.
Every time we push a number, we also push a { min, max } object onto minMaxStack. This object records: "as of right now, what's the smallest and largest number in the stack?"
Every time we pop, we pop from both stacks. The minMaxStack automatically rolls back to the previous min/max state.
Walking through an example
Let's push 3, then 5, then 2:
Push 3: Stack is empty, so 3 is both the min and the max.
stack:[3]minMaxStack:[{ min: 3, max: 3 }]
Push 5: Compare 5 with the current min/max ({ min: 3, max: 3 }). Math.min(3, 5) = 3, Math.max(3, 5) = 5.
stack:[3, 5]minMaxStack:[{ min: 3, max: 3 }, { min: 3, max: 5 }]
Push 2: Compare 2 with the current min/max ({ min: 3, max: 5 }). Math.min(3, 2) = 2, Math.max(5, 2) = 5.
stack:[3, 5, 2]minMaxStack:[{ min: 3, max: 3 }, { min: 3, max: 5 }, { min: 2, max: 5 }]
Now getMin() just reads the top of minMaxStack: 2. getMax() reads 5. No looping.
Pop (removes 2): Pop from both stacks. The top of minMaxStack is now { min: 3, max: 5 }. Min is back to 3, max is still 5.
Pop (removes 5): Pop from both stacks. The top of minMaxStack is now { min: 3, max: 3 }. Both min and max are 3.
See how the minMaxStack automatically "remembers" what the min and max were before each element was added? That's the beauty of this approach. You're recording history so you can roll it back.
Why this works
Each entry in minMaxStack is a snapshot of "what's the min and max for everything from the bottom of the stack up to this point." When you pop an element, you throw away that snapshot and the previous one is revealed, already holding the correct min and max for the remaining elements.
This gives us O(1) for every operation (push, pop, getMin, getMax) at the cost of O(n) extra space for the second stack.
Properties vs Methods
A common interview mistake is confusing array properties and methods. length is a property — you access it without parentheses: arr.length. Methods like push(), pop(), and shift() are functions — they need parentheses to execute. Writing arr.length() throws a TypeError, and writing arr.pop without parentheses returns the function itself instead of calling it.