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
- 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
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
class MinStack {
vector<pair<int, int>> entries;
public:
void push(int value) {
int minimum = entries.empty() ? value : min(value, entries.back().second);
entries.push_back({value, minimum});
}
void pop() { if (!entries.empty()) entries.pop_back(); }
optional<int> top() const {
return entries.empty() ? nullopt : optional<int>(entries.back().first);
}
optional<int> getMin() const {
return entries.empty() ? nullopt : optional<int>(entries.back().second);
}
};
vector<optional<int>> solve(const vector<string>& operations) {
MinStack stack;
vector<optional<int>> output;
for (const auto& op : operations) {
if (op.rfind("push:", 0) == 0) stack.push(stoi(op.substr(5)));
else if (op == "pop") stack.pop();
else output.push_back(op == "top" ? stack.top() : stack.getMin());
}
return output;
}