Min Stack

Q: How do you get the minimum of a stack in O(1) time?

Record the minimum at push time. A stack only changes at its top, so the minimum of the values below any height cannot change while that height is filled. Keep a second stack with the minimum at each height, or only each new minimum, and getMin becomes a read of its top.

Q: Why push onto the min stack when the value equals the current minimum?

Because the minimum can be on the stack more than once. If you record only strictly smaller values, two copies of -2 share one entry in mins . The first pop of -2 removes that entry, and getMin then reports the old minimum although the second -2 is still there. Recording equal values gives each copy its own entry.

Q: Can Min Stack be done with O(1) extra space?

Yes, with one stack and one variable min . When you push an x below the current minimum, store 2x - min instead and set min = x ; the stored number is then smaller than min , which marks it. When a marked number is popped, the previous minimum is 2 * min - stored . The arithmetic overflows 32-bit integers near the limits, so it needs 64-bit values, and the sign logic is error-prone; most interviewers are happy with the two-stack version.

Q: What is the time and space complexity of Min Stack?

Every operation is O(1): push, pop, top and getMin each read or change only the top of one or two stacks. Space is O(n) for n stored values. Storing the minimum beside every value always uses 2n slots; storing only new minimums uses between n + 1 and 2n.

MediumStack

+10

Design a stack that, besides the usual push, pop and top, can report the smallest value it holds with getMin. Each of the four operations must run in O(1) time.

You get the operations in order as ops, with args[i] holding the value for a push and 0 for every other operation. Run them on one stack that starts empty and return one string per operation: "null" for push and pop, and the number as text for top and getMin.

Function

minStackOps(ops: string-array, args: integer-array) → string-array

opsstring-array: the operations, in the order they run
argsinteger-array: the value for each push, 0 for every other operation
Returnsstring-array: one answer per operation, as text

Constraints

1 ≤ ops.length ≤ 3000
args.length == ops.length
Every ops[i] is push, pop, top or getMin.
-2³¹+1 ≤ args[i] ≤ 2³¹-1 for a push, and args[i] == 0 for any other operation.
pop, top and getMin are only called when the stack holds at least one value.

Examples

Input: ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
Output: ["null", "null", "null", "1", "null", "1", "null", "4"]
Explanation: The stack holds 4, 1 and 7 from the bottom up, so the smallest is 1. Popping 7 leaves 1 on top. Popping 1 as well leaves only 4, so the minimum goes back to 4.

Input: ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
Output: ["null", "null", "null", "-2", "null", "-2", "null", "3"]
Explanation: The minimum, -2, is pushed twice. The first pop removes one copy and the other is still there, so getMin stays -2. Only after the second pop does the minimum return to 3.

+16 hidden tests on Submit

Follow-up

Can you build a first in, first out queue that also reports its minimum in O(1) amortized time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A plain stack already does push, pop and top in O(1); the hard part is a minimum that survives pops. The key fact is that a stack only changes at its top: while a value sits at some height, nothing below it can change, so the minimum of everything up to that height is fixed. Write that minimum down when you push and a pop restores the previous one for free. The approaches differ in what they write down.

Scan the stack on every getMin

Intuition

Use an ordinary stack for push, pop and top, and answer getMin by looking at every value it holds and keeping the smallest. This is always right, because it checks the actual contents at the moment of the call.

It breaks the O(1) requirement. A getMin on a stack of n values reads all n of them. The hidden test that pushes 1,500 values with a getMin after each push reads about 1,500 × 1,500 / 2, over a million values, where the other approaches read one per call. A system running 10^5 such operations would read billions.

One cached minimum does not fix it. A variable holding the smallest value works for pushes, but once that value is popped you cannot know the next smallest without scanning again.

Algorithm

Store the values in a list used as a stack.
For push x, append x; for pop, remove the last value; for top, read it.
For getMin, walk through every stored value and return the smallest.
Record each answer as text and return the list.

class MinStack:
    def __init__(self):
        self.values = []

    def push(self, x):
        self.values.append(x)

    def pop(self):
        self.values.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        # Look at every stored value: O(n).
        smallest = self.values[0]
        for v in self.values:
            if v < smallest:
                smallest = v
        return smallest

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Store the minimum beside every value

Intuition

While a value sits at height i of the stack, the values below it cannot change, so the smallest of the bottom i values is fixed for as long as that value is there. Store that number next to each value: a second stack mins where mins[i] is the smallest of values[0..i].

On a push, the new entry of mins is the smaller of x and the entry below it. On a pop, remove the top of both stacks; the top of mins is again the minimum of what is left. getMin reads the top of mins.

In the first example, the pushes 4, 1 and 7 store minimums 4, 1 and 1. Popping 7 leaves 1 on top of mins, and popping 1 leaves 4. Every operation touches only the tops of two stacks, so each one is O(1). The price is a second number for every value.

Algorithm

Keep two stacks of equal height, values and mins.
For push x, push x onto values, and push the smaller of x and the top of mins onto mins (x itself if mins is empty).
For pop, pop both stacks.
For top, read the top of values; for getMin, read the top of mins.
Record each answer as text and return the list.

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []    # mins[i] is the smallest of values[0..i]

    def push(self, x):
        self.values.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))

    def pop(self):
        self.values.pop()
        self.mins.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        return self.mins[-1]

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

A stack of minimums that grows only on a new minimum

Intuition

In the second approach mins often repeats itself: push 1 and then 7, 8 and 9, and mins holds 1, 1, 1, 1. A repeated entry tells you nothing new. So record a value in mins only when it becomes the minimum, and remove it when that same value leaves values.

On a push, add x to mins if mins is empty or x is at most its top. On a pop, if the value leaving values equals the top of mins, pop mins too. The top of mins is always the current minimum: every value pushed after it is either larger, or was at most it, got recorded too, and has been popped since.

The comparison must be <=, not <. In the second example -2 is pushed twice. With < only the first copy is recorded, the first pop removes it from mins, and getMin answers 3 while a -2 is still on the stack. With <= each copy gets its own entry.

All four operations stay O(1). When values arrive from largest to smallest, mins grows as tall as values; when the minimum rarely changes, it stays short.

Algorithm

Keep a stack values and a stack mins.
For push x, push x onto values. If mins is empty or x is at most its top, push x onto mins as well.
For pop, pop values. If the removed value equals the top of mins, pop mins too.
For top, read the top of values; for getMin, read the top of mins.
Record each answer as text and return the list.

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []    # each value that was a minimum when pushed; the top is the current minimum

    def push(self, x):
        self.values.append(x)
        # <= keeps one copy per equal minimum, so popping one leaves the others.
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)

    def pop(self):
        if self.values.pop() == self.mins[-1]:
            self.mins.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        return self.mins[-1]

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Pitfalls and edge cases

The bugs here are about copies of the minimum and about what a pop takes away.

Recording a new minimum only when x is strictly smaller. A second copy of the minimum is then missing from mins, and popping the first copy loses the minimum while the second is still on the stack. The second example catches this.
Keeping the minimum in one variable. It handles pushes, but after the minimum is popped the variable is stale, and finding the next smallest needs a scan.
Comparing boxed integers by reference. In Java, Integer == Integer asks whether both are the same object. That happens to hold for values from -128 to 127, which Java caches, and fails for most larger ones, so the pop check breaks only on big values. Unbox to int first, as the Java code does.
Popping mins on every pop in the third approach. It shrinks only when the removed value is its top; in the second approach the two stacks always move together.
Returning a number for pop. In this format pop returns "null", like push.

Frequently asked questions4

How do you get the minimum of a stack in O(1) time?

Record the minimum at push time. A stack only changes at its top, so the minimum of the values below any height cannot change while that height is filled. Keep a second stack with the minimum at each height, or only each new minimum, and getMin becomes a read of its top.

Why push onto the min stack when the value equals the current minimum?

Because the minimum can be on the stack more than once. If you record only strictly smaller values, two copies of -2 share one entry in mins. The first pop of -2 removes that entry, and getMin then reports the old minimum although the second -2 is still there. Recording equal values gives each copy its own entry.

Can Min Stack be done with O(1) extra space?

Yes, with one stack and one variable min. When you push an x below the current minimum, store 2x - min instead and set min = x; the stored number is then smaller than min, which marks it. When a marked number is popped, the previous minimum is 2 * min - stored. The arithmetic overflows 32-bit integers near the limits, so it needs 64-bit values, and the sign logic is error-prone; most interviewers are happy with the two-stack version.

What is the time and space complexity of Min Stack?

Every operation is O(1): push, pop, top and getMin each read or change only the top of one or two stacks. Space is O(n) for n stored values. Storing the minimum beside every value always uses 2n slots; storing only new minimums uses between n + 1 and 2n.

Python

def minStackOps(ops, args):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]
args = [4, 1, 7, 0, 0, 0, 0, 0]

Expected

["null", "null", "null", "1", "null", "1", "null", "4"]

Min Stack

Function

Constraints

Examples

Hints

Solution

Scan the stack on every getMin

Store the minimum beside every value

A stack of minimums that grows only on a new minimum

Pitfalls and edge cases

Frequently asked questions4

Similar problems