Efficient Minimal Value Retrieval — Problem Statement & Solution Guide
Problem Description
Design a specialized stack data structure that maintains the minimum value of all elements currently in the stack in constant time. The structure must support four core operations: push(x) to add an integer x to the top of the stack, pop() to remove the top element, top() to return the value of the top element without removing it, and getMin() to return the smallest value present in the stack at that moment.
The challenge lies in ensuring that getMin() does not require traversing the entire stack to find the minimum, which would result in O(n) time complexity. Instead, the implementation must track the minimum value dynamically as elements are added and removed, allowing all four operations to execute in O(1) average time complexity.
You are required to implement a class that initializes an empty stack and provides methods for the aforementioned operations. The system must handle negative integers, duplicates, and large sequences of operations efficiently.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Efficient Minimal Value Retrieval"
WHY DOES IT MATTER?
Constant‑time minimum retrieval is a fundamental pattern for any system that needs real‑time analytics on sliding windows, priority queues, or cache eviction policies. It demonstrates mastery over space‑time trade‑offs and the ability to augment classic data structures with auxiliary state.
OPTIMIZATION CHALLENGE
The key insight is to store, with each push, the minimum value up to that depth. This eliminates the need for a full scan on getMin and ensures that pop automatically restores the previous minimum, collapsing both time and space complexities to their theoretical minima.
REAL-WORLD CONNECTION
Think of a stock‑trading platform that continuously receives price ticks. The platform must instantly report the lowest price seen so far without scanning the entire history, similar to how a Min‑Stack keeps the running minimum alongside each new price update.
During an interview, write the auxiliary stack first and keep its synchronization logic simple—push(min(x, aux.top())) and pop both stacks together. This reduces mental overhead and avoids off‑by‑one bugs.
COMPLEXITY AT A GLANCE
O(1) per operationO(n) total, where n is the number of elementsCore Theory — Why This Approach?
The classic Min‑Stack problem requires maintaining the current minimum of a dynamic set while supporting push, pop, top, and getMin in O(1) time. A naive solution would scan the entire stack on each getMin call, leading to O(n) per query and quickly becoming a bottleneck for large input streams, especially in real‑time systems where latency matters. The optimal paradigm leverages auxiliary information stored alongside each element—typically a secondary stack or a paired value that records the minimum up to that point—so that the global minimum can be retrieved instantly without traversing the data structure. This approach exploits the LIFO property of stacks: when an element is popped, the previous minimum is already stored beneath it, guaranteeing constant‑time updates and queries while preserving O(n) overall space, which is optimal for a structure that must remember each element's history.
Interview Questions on This Problem
Q1How would you modify the Min‑Stack to also support retrieving the maximum element in O(1) time?
Maintain two auxiliary stacks: one for the current minimum and another for the current maximum. Each push stores the new element along with the updated min and max (e.g., minStack.push(min(x, minStack.top())) and maxStack.push(max(x, maxStack.top()))). Pop operations synchronize all three stacks, ensuring both getMin() and getMax() run in O(1).
Q2Explain why using a single variable to track the minimum fails when the minimum element is popped.
A single variable only holds the current minimum value, not its history. When the minimum element is removed, the stack loses knowledge of the next smallest element, forcing a full scan to recompute the minimum, which violates the O(1) requirement. The auxiliary stack preserves the previous minima, allowing constant‑time restoration.
Q3Can you implement a Min‑Stack using only one stack and O(1) extra space? If so, describe the technique.
Yes, by encoding previous minima within the stack values themselves. When pushing a new element x that is smaller than the current min, push a special encoded value (2*x - currentMin) and update min to x. When popping, if the popped value is less than the current min, decode the previous min as previousMin = 2*currentMin - encodedValue. This trick preserves O(1) extra space while still offering O(1) operations.
Examples
Input
push(15), push(3), push(7), getMin(), pop(), getMin(), top()
Output
3, 15, 7
Explanation: 1. push(15): Stack is [15], min is 15. 2. push(3): Stack is [15, 3], min is 3. 3. push(7): Stack is [15, 3, 7], min is 3. 4. getMin(): Returns 3. 5. pop(): Removes 7. Stack is [15, 3], min is 3. 6. getMin(): Returns 3. 7. top(): Returns 3.
Input
push(-2), push(-5), push(-1), getMin(), pop(), getMin(), pop(), getMin()
Output
-5, -2, -2
Explanation: 1. push(-2): Stack is [-2], min is -2. 2. push(-5): Stack is [-2, -5], min is -5. 3. push(-1): Stack is [-2, -5, -1], min is -5. 4. getMin(): Returns -5. 5. pop(): Removes -1. Stack is [-2, -5], min is -5. 6. getMin(): Returns -5. 7. pop(): Removes -5. Stack is [-2], min is -2. 8. getMin(): Returns -2.
Input
push(10), push(10), push(10), getMin(), pop(), getMin(), pop(), getMin()
Output
10, 10, 10
Explanation: 1. push(10): Stack is [10], min is 10. 2. push(10): Stack is [10, 10], min is 10. 3. push(10): Stack is [10, 10, 10], min is 10. 4. getMin(): Returns 10. 5. pop(): Removes top 10. Stack is [10, 10], min is 10. 6. getMin(): Returns 10. 7. pop(): Removes top 10. Stack is [10], min is 10. 8. getMin(): Returns 10.
Constraints
- 1 <= number of operations <= 10^5
- -10^9 <= x <= 10^9
- pop(), top(), and getMin() are only called when the stack is not empty
- The total number of push operations will not exceed 10^5
Optimal Approach & Strategy
Maintain an auxiliary stack that records the minimum value at each depth; push and pop synchronize both stacks, allowing getMin to return the top of the auxiliary stack in O(1) time.
Brute Force Approach
Store elements in a regular stack and scan the entire stack on each getMin call to find the smallest value, resulting in O(n) time per query.
Verified Code Solutions
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(x) {
this.stack.push(x);
if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(x);
}
}
pop() {
if (this.stack.length > 0) {
let top = this.stack.pop();
if (top === this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
return top;
} else {
return null;
}
}
getMin() {
if (this.minStack.length > 0) {
return this.minStack[this.minStack.length - 1];
} else {
return null;
}
}
}class MinStack {
public:
MinStack() {
stack = new std::stack<int>();
minStack = new std::stack<int>();
}
void push(int x) {
stack->push(x);
if (minStack->empty() || x <= minStack->top()) {
minStack->push(x);
}
}
int pop() {
if (!stack->empty()) {
int top = stack->top();
stack->pop();
if (top == minStack->top()) {
minStack->pop();
}
return top;
} else {
return -1;
}
}
int getMin() {
if (!minStack->empty()) {
return minStack->top();
} else {
return -1;
}
}
private:
std::stack<int>* stack;
std::stack<int>* minStack;
};class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}
public int pop() {
if (!stack.isEmpty()) {
int top = stack.pop();
if (top == minStack.peek()) {
minStack.pop();
}
return top;
} else {
return -1;
}
}
public int getMin() {
if (!minStack.isEmpty()) {
return minStack.peek();
} else {
return -1;
}
}
}class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, x):
self.stack.append(x)
if not self.minStack or x <= self.minStack[-1]:
self.minStack.append(x)
def pop(self):
if self.stack:
top = self.stack.pop()
if top == self.minStack[-1]:
self.minStack.pop()
return top
else:
return None
def getMin(self):
if self.minStack:
return self.minStack[-1]
else:
return Noneclass MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(x) {
this.stack.push(x);
if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(x);
}
}
pop() {
if (this.stack.length > 0) {
let top = this.stack.pop();
if (top === this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
return top;
} else {
return null;
}
}
getMin() {
if (this.minStack.length > 0) {
return this.minStack[this.minStack.length - 1];
} else {
return null;
}
}
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.