Min Stack LeetCode 155 — O(1) Deep Dive

LeetCode 155 Min Stack asks you to design a data structure that supports four operations: push(val), pop(), top(), and getMin(). The key constraint is that all four operations must run in O(1) time. A standard stack supports push, pop, and top in O(1), but retrieving the minimum element naively requires O(n) time — scanning the entire stack. The challenge is to augment the stack so that getMin is also O(1).

The trick is to store additional information alongside the stack values so that the minimum is always known without any search. Two canonical approaches accomplish this: maintaining a parallel stack that mirrors the minimum at each level of the main stack, or storing the current minimum together with each value as a tuple. A third space-optimised approach encodes the difference between the pushed value and the running minimum, allowing recovery of the previous minimum on pop.

This problem is a staple of system design and data structure interviews because it tests whether candidates can reason about auxiliary state and amortised bookkeeping. Once the core insight — that the minimum must be tracked per-level, not globally — is grasped, the implementation follows directly from first principles.

The two-stack approach maintains two stacks in parallel: a main stack that stores all pushed values in order, and a minStack that tracks the minimum at every level. The minStack top always holds the minimum of all elements currently present in the main stack. When you push a value, you push the value onto the main stack and push min(val, minStack.top) onto the minStack. When you pop, you pop from both stacks simultaneously. getMin simply returns minStack.top.

The insight is that the minStack is not storing the global minimum — it is storing the minimum as seen from each layer of the main stack. If the minimum element is popped from the main stack, the minStack is popped too, and the new minStack top correctly reflects the minimum of the remaining elements. No rebuild or search is ever needed because the minStack has already pre-computed the minimum for every possible stack state.

This approach is clean, easy to explain in an interview, and handles all edge cases without special casing. The only subtlety is initialising the minStack: for the very first push, there is no existing minStack top, so you push val directly. For all subsequent pushes, you push min(val, minStack.top). Both stacks always have the same length, and they must be popped together — breaking this synchronisation is the most common bug.

Push: add val to the main stack. Then push min(val, minStack.top) to the minStack — this records the new running minimum at this stack level. If the minStack is empty (first push), just push val directly as the initial minimum. Both stacks are now one element taller and their tops are consistent.

Pop: pop from the main stack (discarding the top value). Pop from the minStack simultaneously. The new minStack top now reflects the minimum of the remaining elements. top() returns main stack top without popping. getMin() returns minStack top without popping. Every operation is a single push or pop — O(1) with no loops.

The synchronisation invariant — both stacks always have the same length — is what makes correctness provable. Any deviation from this invariant, such as pushing to one stack without the other or forgetting to pop minStack on pop, breaks getMin immediately and is the first thing to check when debugging.

Instead of two separate stacks, you can store tuples of (value, currentMin) on a single stack. Every element pushed onto the stack carries with it the minimum of all elements at or below it. Push appends (val, min(val, stack[-1][1])) or (val, val) if the stack is empty. Pop removes the top tuple. top() returns stack[-1][0]. getMin() returns stack[-1][1].

The tuple approach and the two-stack approach are equivalent in both time and space — O(1) per operation, O(n) total space. The difference is purely syntactic: the tuple approach uses one data structure instead of two. In languages with native tuple or pair support — Python, Kotlin, Swift — the tuple approach is marginally cleaner. In Java or C++, the two-stack approach often reads more clearly because accessing tuple elements via index or getter can obscure intent.

Either approach is acceptable in an interview. State which you are using, explain why the minimum-per-level is stored rather than a global minimum, and the interviewer will be satisfied. The key concept — that the minimum must be preserved at every stack level — is what matters, not the specific implementation vehicle.

The constant-space approach uses a single stack and a scalar variable min to track the running minimum, eliminating the O(n) overhead of the minStack or tuple approach. Instead of storing the actual value, you push (val - min) onto the stack. If val is less than the current min, the pushed difference is negative, which signals that a new minimum was established. The new min is updated to val before pushing.

On pop: if the top of the stack is negative, the element being removed was a minimum. The previous minimum can be recovered as (min - top), and min is updated to this recovered value. If the top is non-negative, min stays unchanged. top() returns min if the top is negative (because the actual value is the current min), otherwise returns (min + top). getMin() always returns min.

This trick achieves O(1) extra space beyond the stack itself, reducing the constant factor for memory. The trade-off is complexity: the encoding logic is non-trivial, prone to integer overflow (val - min can exceed 32-bit bounds for large values), and requires careful explanation in an interview. For most interview settings, the two-stack or tuple approach is preferred for clarity. The difference trick is valuable for follow-up questions about space optimisation.

Python two-stack implementation: class MinStack: def __init__(self): self.stack = []; self.min_stack = []; def push(self, val): self.stack.append(val); self.min_stack.append(val if not self.min_stack else min(val, self.min_stack[-1])); def pop(self): self.stack.pop(); self.min_stack.pop(); def top(self): return self.stack[-1]; def getMin(self): return self.min_stack[-1]. Python lists serve as stacks with append and pop, and the min() call is O(1) with two arguments. The implementation is under 10 lines and needs no imports.

Java two-stack implementation: class MinStack { private Deque<Integer> stack = new ArrayDeque<>(); private Deque<Integer> minStack = new ArrayDeque<>(); public void push(int val) { stack.push(val); minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek())); } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }. ArrayDeque is preferred over Stack in Java as it is faster and avoids synchronisation overhead. Deque.push and Deque.pop operate on the front, equivalent to stack semantics.

Time and space analysis: all four operations — push, pop, top, getMin — are O(1). Space is O(n) where n is the number of elements currently in the stack. In the worst case, every element pushed is a new minimum, so minStack grows in lockstep with the main stack. This is the expected and accepted space complexity. The constant-space trick reduces extra space to O(1) but is not required unless the interviewer asks for a follow-up optimisation.

Max Frequency Stack (LeetCode 895) extends the stack design theme: it requires a pop that removes the most frequently pushed element, with ties broken by recency (the most recently pushed among equal-frequency elements). The solution uses a frequency map and a group map keyed by frequency, maintaining a maxFreq variable that is updated on push and decremented on pop. Like Min Stack, the trick is pre-computing auxiliary state (frequency counts) at push time so that pop is O(1).

Valid Parentheses (LeetCode 20) and Basic Calculator (LeetCode 224) are classic stack problems where the stack models pending computation state. Basic Calculator is the most complex: it handles +, −, (, ) and requires pushing the running result and sign onto a stack when an opening parenthesis is encountered, then popping and combining when a closing parenthesis is encountered. The stack-as-saved-state pattern is a direct generalisation of Min Stack's stack-as-saved-minimum pattern.

The stack design family — Min Stack, Max Frequency Stack, LRU Cache (LeetCode 146), and Insert Delete GetRandom O(1) (LeetCode 380) — all reward the same insight: augment a base data structure with auxiliary bookkeeping updated at write time to make read operations O(1). Recognising this pattern — "what information do I need to maintain as I push, so that my query is free?" — is the key skill tested by these problems.