How do you approach Min Stack (Design)?

A single stack can give you push/pop/top in O(1), but getMin would be O(n) if you scanned every time. You need to track the minimum as you go.

What is the time complexity of Min Stack (Design)?

Time complexity: O(1) per operation.. Space complexity: O(n) for the two stacks, where n is the number of elements currently stored..

What are common mistakes on Min Stack (Design)?

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 (Design)

MediumObject-Oriented Design

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. - `push(x)` pushes element `x` onto the stack. - `pop()` removes the element on top of the stack. - `top()` returns the element on top of the stack. - `getMin()` returns the minimum element currently in the stack. Each of these must run in O(1) time. Implement the function `minStack(operations)` where `operations` is a list of `[op, ...args]`. The supported operations are `["push", x]`, `["pop"]`, `["top"]`, and `["getMin"]`. For `"push"` and `"pop"` return `null`; for `"top"` return the top value; for `"getMin"` return the current minimum. Return the list of results, one per operation (use null for operations that return nothing).

Example 1

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

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

Example 2

Input: operations = [["push",5],["getMin"],["top"],["pop"]]

Output: [null, 5, 5, null]

Example 3

Input: operations = [["push",2],["push",2],["getMin"],["pop"],["getMin"]]

Output: [null, null, 2, null, 2]

Constraints

All operations are valid (no `pop`, `top`, or `getMin` on an empty stack). Values fit in a 32-bit signed integer. There are at most 30000 operations.

Min Stack (Design): 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

A single stack can give you push/pop/top in O(1), but getMin would be O(n) if you scanned every time. You need to track the minimum as you go.
Keep a second stack (a 'min stack') that holds the minimum seen so far at each level. When you push x, push min(x, currentMin) onto it.
On pop, pop from both stacks so the min stack always mirrors the height of the value stack. getMin is then just the top of the min stack.

The optimal approach

Show the approach: The approach

Maintain two parallel stacks: one for the actual values and one (`mins`) where each entry is the minimum of all elements at or below that position. On `push(x)`, push `x` to the value stack and push `min(x, mins.top)` to the min stack. On `pop`, pop both. `top` reads the value stack's top; `getMin` reads the min stack's top. Every operation is O(1).

Time: O(1) per operation.
Space: O(n) for the two stacks, where n is the number of elements currently stored.

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.