How do you approach Min Stack?

Use an auxiliary stack to track the minimum at each level.

What is the time complexity of Min Stack?

Time complexity: O(1) for all operations. Space complexity: O(n).

What are common mistakes on Min Stack?

Popping without first checking the stack is non-empty. Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer. Pushing values where the problem needs indices back.

gitGood.dev

← Back to problems

Min Stack

MediumData Structures

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the `MinStack` class: - `push(val)` pushes the element val onto the stack. - `pop()` removes the element on the top of the stack. - `top()` gets the top element of the stack. - `getMin()` retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function. **Note:** For this problem, implement operations as a function that takes a list of commands and returns the results. Return `null` for void operations (push, pop).

Example 1

Input: operations = [["push",-2],["push",0],["push",-3],["getMin"],["pop"],["top"],["getMin"]]

Output: [null,null,null,-3,null,0,-2]

Explanation: push(-2), push(0), push(-3), getMin() returns -3, pop() removes -3, top() returns 0, getMin() returns -2.

Constraints

- -2^31 <= val <= 2^31 - 1 - Methods pop, top and getMin operations will always be called on non-empty stacks. - At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

Min Stack: approach, complexity and pitfalls

A medium stack problem, graded against 6 test cases (3 of them hidden).

The pattern: Stack

Last-in-first-out processing - matching, nesting, and deferred evaluation.

Reach for it when you see: Balanced brackets, nested structures, undo/back semantics, or expression evaluation.

More Stackproblems →

If you are stuck

Show the 3-step hint ladder

Use an auxiliary stack to track the minimum at each level.
When pushing, also push onto the min stack if the value is <= current minimum.
Alternatively, store pairs of (value, currentMin) in the stack.

The optimal approach

Show the approach: Two Stacks

Maintain a main stack and a min stack. The min stack tracks the minimum value at each level. When pushing, push to the min stack if the value is less than or equal to the current minimum.

Time: O(1) for all operations
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Stack mistakes

These apply to the pattern as a whole, not just this problem.

Popping without first checking the stack is non-empty.
Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer.
Pushing values where the problem needs indices back.