Min Stack: LeetCode 155 Solution Explained

Min Stack (#155) is one of the most deceptively simple problems on LeetCode. The task sounds trivial — design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time. Most candidates know how a stack works. The trick is the getMin() requirement.

This problem is not about stacks alone. It is about data structure augmentation — the idea that you can bolt extra functionality onto an existing structure by storing additional state. Once you see how this works for min stack leetcode, you will recognize the same principle in Max Stack, All O(1) Data Structure, and dozens of other design problems.

In this walkthrough you will learn two clean approaches to the leetcode 155 solution, understand why O(1) getMin is even possible, and internalize the edge cases that trip up candidates in real interviews.

You need to implement a class MinStack that supports four operations. push(val) pushes the element val onto the stack. pop() removes the element on top of the stack. top() returns the top element. getMin() retrieves the minimum element in the stack. All four operations must run in O(1) time.

A regular stack already gives you O(1) push, pop, and top. The challenge is getMin(). Without augmentation, finding the minimum requires scanning every element — that is O(n). The interviewer wants constant time.

The constraint is straightforward: at most 30,000 calls total, and values range from negative 2^31 to 2^31 minus 1. pop, top, and getMin will always be called on a non-empty stack. This means you do not need to handle empty-stack edge cases for those three operations.

The two-stack approach is the most intuitive min stack implementation. You maintain two stacks: the main stack that holds all pushed values, and a min stack that tracks the current minimum at each level of depth.

When you push a value, it always goes onto the main stack. For the min stack, you push the value only if it is less than or equal to the current minimum (the top of the min stack). If the min stack is empty, you push regardless. When you pop, you remove from the main stack. If the popped value equals the top of the min stack, you pop the min stack too.

getMin() simply returns the top of the min stack — a single peek operation, O(1). top() returns the top of the main stack. Both stacks stay synchronized so the min stack always reflects the minimum of whatever elements are currently in the main stack.

The time complexity is O(1) for all four operations. The space complexity is O(n) in the worst case — if you push a strictly decreasing sequence, every element lands on both stacks.

Instead of two separate stacks, you can use a single stack where each entry stores a pair: the value itself and the current minimum at that stack depth. Every push computes the new minimum as the smaller of the incoming value and the previous top pair minimum.

When you push the first element, the pair is (val, val) since that element is the only one and therefore the minimum. For subsequent pushes, the pair is (val, min(val, stack.top().currentMin)). Each entry carries its own snapshot of the minimum.

pop() just removes the top pair. top() returns the value component of the top pair. getMin() returns the currentMin component of the top pair. All O(1), all from a single data structure.

This approach trades a tiny bit of per-element space overhead (storing the min alongside every value) for conceptual simplicity. In practice, both approaches use O(n) space. The pairs approach is often easier to implement without bugs because there is no conditional logic — you always push, you always pop, and the min is always right there.

The key insight behind every constant time min stack solution is this: the minimum can only change when you push or pop. Between those operations, the minimum is static. There is no random insertion or deletion in the middle of the stack — elements only enter and leave from the top.

Because of this LIFO property, you can track the minimum incrementally. Each time you push, you check if the new element is smaller than the current min and update accordingly. Each time you pop, the previous minimum is already stored — either on the min stack or in the pair below the top.

This is fundamentally different from a structure like an unsorted array where any element can be removed. In that case, removing the minimum forces a rescan. With a stack, you always know which element leaves next (the top), and you have already precomputed what the minimum will be after it leaves.

This principle generalizes. If you need any aggregate statistic (max, sum, count of distinct elements) that only changes on push and pop, you can track it the same way. The min stack design pattern is the gateway to a family of augmented data structures.

The most common bug in min stack implementation is mishandling duplicate minimums. If you push 0, then push another 0, the min stack must contain two 0s. When you pop one 0, the minimum is still 0. If you used strict less-than when deciding whether to push to the min stack, you would only push one 0, and after popping it, the min stack would be wrong.

Negative numbers are another source of confusion. The minimum can be a large negative value, and pushing a less-negative value should not update the min. Make sure your comparison logic handles negatives correctly — it usually does if you use standard less-than, but test explicitly.

The problem guarantees that pop, top, and getMin are only called on non-empty stacks. However, in an interview, you might be asked what happens if someone calls getMin on an empty stack. Decide upfront: throw an error, return infinity, or return undefined. The interviewer wants to see you think about it.

Finally, consider Integer.MIN_VALUE. If someone pushes the minimum possible integer, your min tracking still works — it is just another value. But if you initialized your min to Integer.MIN_VALUE as a sentinel, you would have a collision. Use the stack-based approach (two stacks or pairs) to avoid sentinel values entirely.

Min Stack is not just a stack problem. It is your introduction to data structure augmentation — the technique of adding functionality to an existing structure by storing extra state alongside the primary data. The extra state (the minimum) is maintained incrementally so it never requires a full scan.

This same principle appears in harder problems. Max Stack asks you to support popMax() efficiently. The All O(1) Data Structure problem requires O(1) inc, dec, getMaxKey, and getMinKey. LRU Cache combines a hash map with a doubly linked list. In each case, the core idea is the same: store redundant information that makes expensive queries instant.

For interview prep, min stack leetcode is the problem that makes this click. Once you solve it cleanly, you have the mental model for every augmented data structure question. Practice both the two-stack and pairs approaches until you can write either from memory in under five minutes.

Review Min Stack regularly with YeetCode flashcards to keep the pattern sharp. The design problems build on each other — if you forget the foundation, the harder variants become exponentially more difficult.