Min Stack
- mosesg1123
- 4 days ago
- 4 min read
Maintaining a stack that can return its minimum value in constant time is a neat warm‑up that mirrors real‑world needs like tracking the lowest price in a financial time series or monitoring health metrics. It tests your ability to augment a basic data structure with an auxiliary mechanism for fast queries.
Problem Statement
Design a stack that supports the following operations in O(1) time:
push(x): Push element x onto the stack.
pop(): Remove the element on top of the stack.
top(): Get the top element.
getMin(): Retrieve the minimum element in the stack.
Implement the MinStack class with these methods.
1. Clarify Requirements Before Jumping Into Code
Can values be negative or very large? Yes, any integer.
Will pop, top, or getMin be called on an empty stack? We can assume the interviewer won’t do that, or we can throw an exception.
Do duplicate values need special handling? Yes—if the minimum value is pushed multiple times, pop must restore the previous minimum correctly.
Should all operations be amortized O(1)? Yes, worst‑case O(1) is ideal.
2. Identify the Category of the Question
This is a design problem for an augmented stack data structure. Common patterns include:
Auxiliary stack to track extra state (min, max)
Pair or tuple storage per element (value and auxiliary info)
Difference encoding to store only deltas and a current min
Linked‑list with extra fields per node
Recognizing the need for getMin() in O(1) suggests storing historical minima alongside the main values.
3. Consider a Brute‑Force Approach to Understand the Problem
The simplest approach is to use a normal stack and, on each getMin(), scan all elements to find the minimum.
Time Complexity:
push, pop, top: O(1)
getMin: O(n)
Space Complexity: O(n)
Drawback: getMin is O(n), too slow for repeated calls.
This confirms correctness but highlights performance limitations.
4. Brainstorm More Solutions
Store Min with Each Node (Pair Stack): Push a (value, currentMin) pair so that getMin() just returns the second element of the top pair.
Pros: All operations O(1), simple to derive.
Cons: Extra space of 2× for each element.
Two-Stack Approach: I need to remember every historical min so that when the current min is popped, I restore the previous one. A natural way is to push minima onto a second stack exactly when they become the new minimum. That way, getMin is always the top of the min‑stack, and popping restores the prior min.
On push(x), push x to primary-stack; push x to min‑stack if it’s ≤ current min.
On pop(), pop main; if popped value == min‑stack top, pop min‑stack.
getMin() reads min‑stack top.
Pros: O(1) ops, secondary stack only stores a subset of values.
Cons: Slightly more code to manage two stacks.
Difference Encoding (Optimal, Single Stack): Store in the main stack the difference x - currentMin, and update currentMin when pushing or popping negative deltas.
Pros: Uses a single stack and O(1) extra variables.
Cons: Arithmetic is tricky under pressure and can overflow if not careful.
To derive the two‑stack solution in real time, I’d think:
5. Discuss Trade‑Offs Between Your Solutions
Approach | Time | Space | Pros | Cons |
Brute‑Force Scan on getMin | push/pop/top O(1), getMin O(n) | O(n) | Very simple | getMin too slow |
Pair Stack (value,min) | O(1) each | 2× O(n) | Simple codeAll ops O(1) | Doubles per-element storage |
Two‑Stack | O(1) each | O(n) + ≤O(n) | Balanced spaceAll ops O(1) | Needs to sync two stacks |
Difference Encoding | O(1) each | O(n) + O(1) vars | Minimal extra memory | Complex logic, overflow risk |
The two‑stack approach is clear, efficient, and safe under interview time constraints.
6. Write Pseudocode to Structure Your Thoughts
initialize mainStack as empty
initialize minStack as empty
function push(x):
mainStack.push(x)
if minStack empty or x <= minStack.peek():
minStack.push(x)
function pop():
val = mainStack.pop()
if val == minStack.peek():
minStack.pop()
function top():
return mainStack.peek()
function getMin():
return minStack.peek()
7. Consider Edge Cases
No elements: empty state; top/getMin undefined—interviewer won’t call.
All pushes are increasing: minStack only stores first element.
All pushes are decreasing: minStack mirrors every push.
Duplicates of minimum: minStack stores duplicates so that one pop restores the same min if needed.
Interleaved pushes/pops: operations sync correctly between stacks.
8. Write Full Code Syntax (in Java)
import java.util.Stack;
public class MinStack {
private Stack<Integer> mainStack;
private Stack<Integer> minStack;
public MinStack() {
mainStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
mainStack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}
public void pop() {
int val = mainStack.pop();
if (val == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return mainStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
9. Test Your Code
public static void main(String[] args) {
MinStack ms = new MinStack();
ms.push(-2);
ms.push(0);
ms.push(-3);
assert ms.getMin() == -3; // min is -3
ms.pop(); // removes -3
assert ms.top() == 0; // top is now 0
assert ms.getMin() == -2; // min is back to -2
// Test with duplicates
ms = new MinStack();
ms.push(2);
ms.push(2);
ms.push(1);
ms.push(1);
assert ms.getMin() == 1;
ms.pop();
assert ms.getMin() == 1; // duplicate 1 remains
ms.pop();
assert ms.getMin() == 2; // both 1s popped
// Test increasing sequence
ms = new MinStack();
ms.push(1);
ms.push(2);
ms.push(3);
assert ms.getMin() == 1;
ms.pop();
ms.pop();
assert ms.getMin() == 1;
System.out.println("All tests passed!");
}
10. Key Lessons to Remember for Future Questions
Auxiliary structure: Pair a secondary stack to track extra state (min in this case).
Sync operations: Always mirror push/pop logic between main and auxiliary stacks.
Handle duplicates: Push to the min stack even when equal to current min so equal values are popped correctly.
Amortized O(1): All operations run in constant time overall; worst‑case a single push or pop may affect both stacks but stays O(1).
Pseudocode first: Sketching two‑stack logic prevents pointer/stack errors under time pressure.
Edge cases: Test no-op and duplicate-min scenarios to verify auxiliary synchronization.
You'll notice we didn't choose to implement the memory-optimal solution here. Sometimes that's ok! Just be prepared to explain why you're making that choice in the interview, and make it clear to your interviewer that you still understand the optimal solution and could implement it if necessary.
Good Luck and Happy Coding!
Comments