Coder's Cat

LeetCode: Min Stack


LeetCode Challenge Description: Min Stack

Solution with Stack

Note the requirement of retrieving the minimum element in constant time. For this purpose, we need to use a extra space to store the current minimum element with different top values in in the stack.

#include <stack>
using namespace std;

class MinStack {
stack<pair<int, int> > s;
MinStack() { }

void push(int x) {
if(s.empty()) {
s.push(std::make_pair(x, x));
} else {
int n = min(x, getMin());
s.push(std::make_pair(x, n));

void pop() {

int top() {
pair<int, int> t =;
return t.first;

int getMin() {
pair<int, int> t =;
return t.second;

Preparing for an interview? Check out this!