Log inSign up
mediumLeetCodeNot Started

Min Stack

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class: * MinStack() initializes the stack object. * void push(int val) pushes the element val onto the stack. * void pop() removes the element on the top of the stack. * int top() gets the top element of the stack. * int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1 · Standard MinStack Operations:

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Explanation: minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints:

  • -231 <= val <= 231 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why searching the stack for the minimum violates the O(1) requirement and how state pairing solves it.
  • Master the mathematical encoding trick 2 * x - min to achieve O(1) extra space.
  • Handle 64-bit integer overflow correctly during difference encoding.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Method 1 (Pairs): Each stack entry holds (value, minAtThisState).
  • Method 2 (Auxiliary Stack): Maintain a secondary stack tracking strictly non-increasing minimums.
  • Method 3 (Mathematical Encoding): Push 2 * val - min when a new min is created, avoiding extra space.

Connected Patterns:

Max StackImplement Queue using StacksOnline Stock Span

1. Single Vector with Linear getMin Search

Intuition

Store values in a single standard stack/array. When getMin() is invoked, linearly scan all elements to find and return the minimum.

Algorithm

  1. Step 1: Store elements in dynamic array st.
  2. Step 2: push(x) -> st.push_back(x).
  3. Step 3: pop() -> st.pop_back().
  4. Step 4: top() -> st.back().
  5. Step 5: getMin() -> iterate through st and return the minimum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class MinStack {
6 std::vector<int> st;
7public:
8 MinStack() {}
9
10 void push(int val) {
11 st.push_back(val);
12 }
13
14 void pop() {
15 st.pop_back();
16 }
17
18 int top() {
19 return st.back();
20 }
21
22 int getMin() {
23 return *std::min_element(st.begin(), st.end());
24 }
25};
26
27int main() {
28 MinStack minStack;
29 minStack.push(-2);
30 minStack.push(0);
31 minStack.push(-3);
32 std::cout << "Min: " << minStack.getMin() << std::endl; // -3
33 minStack.pop();
34 std::cout << "Top: " << minStack.top() << std::endl; // 0
35 std::cout << "Min: " << minStack.getMin() << std::endl; // -2
36 return 0;
37}

Time & Space Complexity

  • Time complexity: push/pop/top: O(1), getMin: O(N) — getMin searches through all elements in the vector taking O(N) time.
  • Space complexity: O(N) — O(N) space to store elements.

Why Brute Force Doesn't Scale:

Linear getMin search costs O(N) per call, timing out under 30,000 operations.

Optimal MinStack handles 30,000 mixed calls in <5ms.

2. Pair Stack / Two Parallel Stacks

Intuition

Store (val, currentMin) together in each stack entry. The current minimum is simply min(val, top.currentMin).

Algorithm

  1. Step 1: In push(val): if stack is empty, push (val, val). Otherwise push (val, min(val, st.top().min)).
  2. Step 2: In pop(): pop the top pair.
  3. Step 3: In top(): return st.top().val.
  4. Step 4: In getMin(): return st.top().min.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3#include <algorithm>
4
5class MinStack {
6 std::stack<std::pair<int, int>> st; // {value, currentMin}
7public:
8 MinStack() {}
9
10 void push(int val) {
11 int currentMin = st.empty() ? val : std::min(val, st.top().second);
12 st.push({val, currentMin});
13 }
14
15 void pop() {
16 st.pop();
17 }
18
19 int top() {
20 return st.top().first;
21 }
22
23 int getMin() {
24 return st.top().second;
25 }
26};
27
28int main() {
29 MinStack minStack;
30 minStack.push(-2);
31 minStack.push(0);
32 minStack.push(-3);
33 std::cout << "Min: " << minStack.getMin() << std::endl; // -3
34 minStack.pop();
35 std::cout << "Top: " << minStack.top() << std::endl; // 0
36 std::cout << "Min: " << minStack.getMin() << std::endl; // -2
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(1) All Operations — Every stack node records the minimum element present in the stack up to that level, giving instant O(1) getMin.
  • Space complexity: O(2N) — Stores 2 values per element (value and current minimum).

3. Optimal O(1) Auxiliary Space Encoded Stack

Intuition

Store only 1 integer per element. When val < minVal, push the encoded value 2 * val - minVal (which is guaranteed to be strictly less than val), and update minVal = val. Upon popping, if popped < minVal, restore prevMin = 2 * minVal - popped.

Algorithm

  1. Step 1: Maintain a 64-bit integer stack st and variable minVal.
  2. Step 2: In push(val): if empty, set minVal = val, push val. If val >= minVal, push val. Else, push 2 * (long long)val - minVal and set minVal = val.
  3. Step 3: In pop(): if st.top() < minVal, restore minVal = 2 * minVal - st.top(), then pop.
  4. Step 4: In top(): if st.top() < minVal, return minVal (since minVal was the original value). Else return st.top().
  5. Step 5: In getMin(): return minVal.

MinStack Operations Execution Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
Current operationSTEP 1 OF 7
minVal = -2
Visual state
Values and pointers at this exact step
stack
TOP
-2 (min: -2)
Push adds to the top · Pop removes from the top
Why this step matters

minVal = -2

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4class MinStack {
5 std::stack<long long> st;
6 long long minVal;
7public:
8 MinStack() {}
9
10 void push(int val) {
11 if (st.empty()) {
12 st.push(val);
13 minVal = val;
14 } else if (val >= minVal) {
15 st.push(val);
16 } else {
17 st.push(2LL * val - minVal);
18 minVal = val;
19 }
20 }
21
22 void pop() {
23 if (st.top() < minVal) {
24 minVal = 2 * minVal - st.top();
25 }
26 st.pop();
27 }
28
29 int top() {
30 if (st.top() < minVal) {
31 return minVal;
32 }
33 return st.top();
34 }
35
36 int getMin() {
37 return minVal;
38 }
39};
40
41int main() {
42 MinStack minStack;
43 minStack.push(-2);
44 minStack.push(0);
45 minStack.push(-3);
46 std::cout << "Min: " << minStack.getMin() << std::endl; // -3
47 minStack.pop();
48 std::cout << "Top: " << minStack.top() << std::endl; // 0
49 std::cout << "Min: " << minStack.getMin() << std::endl; // -2
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(1) All Operations — All operations execute in single-step mathematical evaluations with O(1) time.
  • Space complexity: O(N) (1 value per element) — Strictly O(N) memory without storing pairs or auxiliary parallel stacks.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Single Vector with Linear Scanpush/pop/top: O(1), getMin: O(N)O(N)Standard stack with linear scan on getMin.Linear scan on getMin calls.
2.Pair Stack (Two Parallel Stacks)O(1) All OperationsO(2N)Store (val, currentMin) pair with every stack node.Auxiliary space.
3.Optimal Encoded StackOptimalO(1) All OperationsO(N)Mathematical transformation 2*val - minVal preserves history without extra space.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using 32-bit int in C++/Java for 2 * val - minVal, causing integer overflow on extreme values.

Pitfall 2:

Returning the encoded value in top() instead of minVal when st.top() < minVal.

Pitfall 3:

Forgetting to restore minVal upon popping an encoded element.

Crucial Edge Cases to Validate:

  • Pushing integer minimum `-2^31` and maximum `2^31 - 1` — Handled without overflow via 64-bit types.
  • All pushed elements equal — Minimum never changes; regular values pushed.
  • Strictly decreasing sequence — Every push encodes a new minimum; every pop restores previous minimum.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always start by explaining the Pair / Two-Stack approach first (O(2N) space) to show clean, robust design.
  2. Then introduce the mathematical encoding 2*x - min as an advanced space optimization down to O(N).
  3. Explicitly highlight 64-bit integer overflow handling during mathematical encoding.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does 2 * val - minVal allow us to recover the previous minimum upon popping?

2.Why must we use 64-bit integers (long long / BigInt) for the mathematical encoding approach?

Back to DSA Sheet