Skip to main content
SeniorPath
Browse content
Menu / Close menu

March 24

Min Stack

How to keep the minimum updated in O(1) with a simple helper structure instead of scanning the whole stack.

Stack Intermediate 15 min TypeScript

#interviews#stack#design

Implement a stack that supports:

  • push(x)
  • pop()
  • top()
  • getMin()

All operations must run in O(1).

In the original problem, this is usually a class. In the SeniorPath playground, use:

  • operations: the list of operations
  • values: the value associated with each operation, or null when there is none

And return an array with the result of each operation. Operations that do not return a value should return null.

Example:

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

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

What to notice before coding

  • The hard part is not pushing and popping. It is keeping the minimum always ready.
  • The minimum changes together with `push` and `pop`.
  • The key idea is maintaining a synchronized helper invariant.

Common mistakes

  • scanning the whole stack on every `getMin`
  • forgetting to update the helper structure on `pop`

Step 1 - Understand what is actually difficult

A normal stack already makes these easy:

  • push
  • pop
  • top

The real point of the problem is:

  • how do you answer getMin() in O(1)?

Step 2 - Write the most direct baseline

The natural baseline is:

  • keep a normal stack
  • when getMin appears, scan the whole stack for the minimum

It works.

But getMin becomes O(n).

Step 3 - Ask what information must stay ready

At each stack position, what matters is not only the current value.

What also matters is:

  • what is the minimum value up to this point?

Step 4 - Turn that into an invariant

The simple approach is a second stack:

  • stack stores the values
  • mins stores the minimum value for each depth

That way, the top of mins is always the answer to getMin.

The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.

Starter code

export function runMinStack(operations, values) {
  // operations example: ["MinStack", "push", "getMin"]
  // values example: [null, 3, null]
  // your solution here
  return []
}
solution.ts
Stuck? Hints available.

Haven't solved it yet?

Viewing the solution now may reduce learning. It's worth trying a bit more.

Open the reference solution

Without JavaScript, the reference solution is shown inline instead of in a dialog.

Solution

Final complexity

Time: O(1)

Space: O(n)

Solution 1 - Simple stack plus scan on getMin

Good baseline because it makes the bottleneck obvious.

export function runMinStack(operations, values) {
  const stack = []
  const output = []

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "MinStack") {
      output.push(null)
    } else if (operation === "push") {
      stack.push(value)
      output.push(null)
    } else if (operation === "pop") {
      stack.pop()
      output.push(null)
    } else if (operation === "top") {
      output.push(stack[stack.length - 1] ?? null)
    } else if (operation === "getMin") {
      output.push(Math.min(...stack))
    }
  }

  return output
}

It works, but getMin is too expensive because it turns into O(n).

Solution 2 - Helper stack of minimums

Now the derived information stays ready all the time.

export function runMinStack(operations, values) {
  const stack = []
  const mins = []
  const output = []

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "MinStack") {
      output.push(null)
    } else if (operation === "push") {
      stack.push(value)

      const currentMin = mins.length === 0 ? value : Math.min(value, mins[mins.length - 1])
      mins.push(currentMin)
      output.push(null)
    } else if (operation === "pop") {
      stack.pop()
      mins.pop()
      output.push(null)
    } else if (operation === "top") {
      output.push(stack[stack.length - 1] ?? null)
    } else if (operation === "getMin") {
      output.push(mins[mins.length - 1] ?? null)
    }
  }

  return output
}

The central idea is the invariant: mins[i] always represents the minimum among the first i + 1 elements.

What to say in the interview

A strong short explanation would be:

A normal stack handles push, pop, and top, but not getMin in O(1) if I have to scan everything. So I keep a second synchronized stack of minimums. Each position stores the minimum value up to that point. Then getMin becomes just reading the top of that helper stack.

That shows that you:

  • identified exactly which operation breaks the complexity
  • answered it with a simple invariant
  • explained the design without theater

When this pattern shows up again

The same pattern comes back when you need to:

  • keep derived information always ready
  • design a structure under complexity constraints
  • synchronize main state with helper state
  • think in per-operation invariants

The point is not memorizing MinStack.

The point is learning to keep the answer ready while the structure changes.
Next challenge Implement Queue using Stacks Previous challenge Top K Frequent Elements

Related challenges

Valid Parentheses

Longest Substring Without Repeating Characters

3Sum

Related articles

Thinking Before You Code in Interviews

How to Explain Your Solution Without Getting Lost

Recognizing Problem Patterns