Workspace

Problem workspace

3 day streakD

Min Stack

MediumStacksStack foundations

The challenge

Implement push, pop, top, and getMin, with each operation taking constant time.

Operations use push:value, pop, top, min. Queries and pop on an empty stack return null.

Example

push:-2, push:0, push:-3, min, pop, top, min → [-3, 0, -2].

Use the walkthrough below to inspect the input and each state change.

See Min Stack, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.push…0push…1push…2min3pop4top5min6Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 9

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: ["push:-2","push:0","push:-3","min","pop","top","min"]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

Each entry stores (value, minimum so far).

Indices are zero-based. C++ uses C++17 or later.

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

    def push(self, value):
        minimum = min(value, self.stack[-1][1]) if self.stack else value
        self.stack.append((value, minimum))

    def pop(self):
        if self.stack:
            self.stack.pop()

    def top(self):
        return self.stack[-1][0] if self.stack else None

    def get_min(self):
        return self.stack[-1][1] if self.stack else None


def solve(operations):
    stack, output = MinStack(), []
    for token in operations:
        op, _, raw = token.partition(':')
        if op == 'push': stack.push(int(raw))
        elif op == 'pop': stack.pop()
        elif op == 'top': output.append(stack.top())
        else: output.append(stack.get_min())
    return output

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap