These are the notes for DSA episode 29: two classic stack problems. A min stack is a stack that also answers "what is the smallest value in here?" in O(1). Scanning the stack on every getMin is O(n) per call and times out on 2 lakh operations; one min variable gives a wrong answer after a pop. The fix: every entry remembers the minimum below it, using a second stack of minimums. Reverse Polish notation (postfix) writes the operator after its operands; evaluating it by repeatedly finding the first operator and splicing the list is O(n²), while one operand stack does it in a single O(n) pass. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
Min stack. A teacher checks answer sheets and puts each one on top of a pile; sometimes she takes the top sheet back off to re-check it. The principal keeps asking: "what's the lowest mark in the pile right now?" Flipping through all 500 sheets every time is slow. The smart teacher sticks a note on every sheet as she adds it: "lowest mark from this sheet down". The answer is always on the top sheet.
| In the staff room | In the code |
|---|---|
| The pile of answer sheets | The stack (st) |
| Putting a sheet on top / taking it back | push(x) / pop() |
| "Lowest mark in the pile?" | getMin() |
| Flipping through every sheet | Scanning the stack: O(n) |
| The sticky note "lowest from here down" | The second stack mins |
Reverse Polish notation. Old adding machines at billing counters worked like this: enter 20, enter 15, then press +, and 35 is printed. Numbers first, operation after: no brackets and no = key.
| On the adding machine | In the code |
|---|---|
| Entering a number | Pushing an operand |
| Pressing + | Pop two operands, push their sum |
| The paper roll | The final value on the stack |
Problem statements
Min stack (LeetCode 155). Design a stack that supports push(x), pop(), top() and getMin(), each in O(1) time.
push(-2) push(0) push(-3)
getMin() → -3
pop()
top() → 0
getMin() → -2
Evaluate reverse Polish notation (LeetCode 150). Given tokens, an array of strings forming a valid postfix expression with + - * / and integers, return its value. Division truncates toward zero.
"2 1 + 3 *" → 9 ((2 + 1) * 3)
"4 13 5 / +" → 6 (4 + 13 / 5)
"10 6 9 3 + -11 * / * 17 + 5 +" → 22
Edge cases: min stack with a duplicate minimum (push 3, 1, 1, pop once: the minimum is still 1); a single number ("42" → 42); negative operands like -11; 7 / -2 → -3 (truncation, not floor).
Part 1 brute force: scan the stack on every getMin
Keep the values in an ArrayList; push and pop work at the end, and getMin walks the whole list.
import java.util.*;
public class Main {
static ArrayList<Integer> st = new ArrayList<>();
static void push(int x) { st.add(x); }
static void pop() { st.remove(st.size() - 1); }
static int top() { return st.get(st.size() - 1); }
static int getMin() {
int m = st.get(0);
for (int x : st) m = Math.min(m, x);
return m;
}
public static void main(String[] args) {
push(-2); push(0); push(-3);
System.out.println(getMin());
pop();
System.out.println(top());
System.out.println(getMin());
}
}
Output:
-3
0
-2
The big input: 2 lakh pushes
Push 200000, 199999, …, 1 and call getMin() after every push:
int n = 200000;
long t0 = System.nanoTime(), sum = 0;
for (int i = 0; i < n; i++) {
push(n - i);
sum += getMin();
}
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("sum " + sum + ", " + ms + " ms");
The brute force gets Time Limit Exceeded: the k-th getMin reads k values, so the total is about n²/2 = 2 × 10¹⁰ steps.
The tempting fix: one min variable
static ArrayList<Integer> st = new ArrayList<>();
static int min = Integer.MAX_VALUE;
static void push(int x) { st.add(x); min = Math.min(min, x); }
static void pop() { st.remove(st.size() - 1); }
static int top() { return st.get(st.size() - 1); }
static int getMin() { return min; }
On the same example it prints -3, 0, -3. Wrong: after popping -3, the variable still remembers it, and a single variable has no record of what the minimum was before.
Part 1 key insight: every entry remembers the minimum below it
Store, next to every entry, the minimum of that entry and everything below it. A second stack mins moves together with st:
push(x): pushxonst, and pushmin(x, mins.top)onmins(justxifminsis empty).pop(): pop both stacks.getMin(): the top ofmins. O(1).- After a pop, the new top of
minsalready holds the minimum without the popped value: nothing is recomputed.
Dry run:
| Operation | st (bottom → top) |
mins (bottom → top) |
Answer |
|---|---|---|---|
| push(-2) | -2 | -2 | |
| push(0) | -2, 0 | -2, -2 | |
| push(-3) | -2, 0, -3 | -2, -2, -3 | |
| getMin() | -3 | ||
| pop() | -2, 0 | -2, -2 | |
| top(), getMin() | 0, -2 |
Part 1 optimal solution in Java
import java.util.*;
public class Main {
static Deque<Integer> st = new ArrayDeque<>();
static Deque<Integer> mins = new ArrayDeque<>();
static void push(int x) {
st.push(x);
mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
}
static void pop() { st.pop(); mins.pop(); }
static int top() { return st.peek(); }
static int getMin() { return mins.peek(); }
public static void main(String[] args) {
push(-2); push(0); push(-3);
System.out.println(getMin());
pop();
System.out.println(top() + " " + getMin());
pop(); pop();
push(3); push(1); push(1);
pop();
System.out.println(getMin());
pop();
System.out.println(getMin());
}
}
Output:
-3
0 -2
1
3
On LeetCode the same methods go inside class MinStack as instance methods. With the 2 lakh pushes, it prints sum 20000100000, 180 ms: every getMin is one peek.
Part 2 brute force: do it like on paper
Find the first operator from the left, replace it and its two operands with the result, repeat until one token is left: 2 1 + 3 * → 3 3 * → 9.
import java.util.*;
public class Main {
static String[] T(String s) { return s.split(" "); }
static boolean isOp(String s) { return "+-*/".contains(s); }
static int calc(int a, int b, String op) {
return switch (op) {
case "+" -> a + b; case "-" -> a - b;
case "*" -> a * b; default -> a / b;
};
}
static int brute(String[] tk) {
List<String> t = new ArrayList<>(Arrays.asList(tk));
while (t.size() > 1) {
int i = 0;
while (!isOp(t.get(i))) i++;
int a = Integer.parseInt(t.get(i - 2));
int b = Integer.parseInt(t.get(i - 1));
t.set(i - 2, "" + calc(a, b, t.get(i)));
t.remove(i);
t.remove(i - 1);
}
return Integer.parseInt(t.get(0));
}
public static void main(String[] args) {
System.out.println(brute(T("2 1 + 3 *")));
System.out.println(brute(T("4 13 5 / +")));
}
}
Output: 9 and 6. (isOp uses "+-*/".contains(s): a lone - is an operator, but -11 is not a substring of +-*/, so it is an operand.)
The big input: 1 lakh ones and 99,999 pluses
int n = 100000;
String[] tk = new String[2 * n - 1];
Arrays.fill(tk, 0, n, "1");
Arrays.fill(tk, n, 2 * n - 1, "+");
The answer is 100000, but the brute force gets Time Limit Exceeded.
Why the brute force fails
- Every round scans from the left to find the first operator: with up to a lakh ones in front, O(n) per round.
ArrayList.remove(i)shifts every later token one place left: another O(n).- About n rounds: O(n²).
The clue: when an operator arrives, its operands are always the last two values seen (numbers, or results just made). Last in, first used: a stack.
Part 2 key insight: one operand stack
- A number: push it.
- An operator:
b = pop()first (it was pushed last, so it is the right operand), thena = pop(). - Push
a op b. Order matters for-and/. - At the end the stack holds exactly one value: the answer.
Dry run on 4 13 5 / +:
| Token | Action | Stack (bottom → top) |
|---|---|---|
| 4 | push | 4 |
| 13 | push | 4, 13 |
| 5 | push | 4, 13, 5 |
| / | b = 5, a = 13, 13 / 5 = 2 | 4, 2 |
| + | b = 2, a = 4, 4 + 2 = 6 | 6 |
Part 2 optimal solution in Java
static int evalRPN(String[] tokens) {
Deque<Integer> st = new ArrayDeque<>();
for (String s : tokens) {
if (isOp(s)) {
int b = st.pop(), a = st.pop();
st.push(calc(a, b, s));
} else {
st.push(Integer.parseInt(s));
}
}
return st.pop();
}
public static void main(String[] args) {
System.out.println(evalRPN(T("2 1 + 3 *")));
System.out.println(evalRPN(T("4 13 5 / +")));
System.out.println(evalRPN(T("10 6 9 3 + -11 * / * 17 + 5 +")));
System.out.println(evalRPN(T("42")));
System.out.println(evalRPN(T("7 -2 /")));
}
(T, isOp and calc are the same helpers as in the brute force.) Output:
9
6
22
42
-3
On the 2 lakh tokens it prints 100000, 197 ms.
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
class MinStack {
stack<int> st, mins;
public:
void push(int x) {
st.push(x);
mins.push(mins.empty() ? x : min(x, mins.top()));
}
void pop() { st.pop(); mins.pop(); }
int top() { return st.top(); }
int getMin() { return mins.top(); }
};
int evalRPN(const vector<string>& tokens) {
stack<int> st;
for (const string& s : tokens) {
if (s == "+" || s == "-" || s == "*" || s == "/") {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
if (s == "+") st.push(a + b);
else if (s == "-") st.push(a - b);
else if (s == "*") st.push(a * b);
else st.push(a / b); // C++ also truncates toward zero
} else {
st.push(stoi(s));
}
}
return st.top();
}
int main() {
MinStack ms;
ms.push(-2); ms.push(0); ms.push(-3);
cout << ms.getMin() << "\n"; // -3
ms.pop();
cout << ms.top() << " " << ms.getMin() << "\n"; // 0 -2
cout << evalRPN({"2", "1", "+", "3", "*"}) << "\n"; // 9
cout << evalRPN({"4", "13", "5", "/", "+"}) << "\n"; // 6
cout << evalRPN({"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}) << "\n"; // 22
cout << evalRPN({"7", "-2", "/"}) << "\n"; // -3
}
Note: in C++, stack::pop() returns nothing, so read top() first, then pop().
The same solutions in Python
class MinStack:
def __init__(self):
self.st, self.mins = [], []
def push(self, x):
self.st.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.st.pop()
self.mins.pop()
def top(self):
return self.st[-1]
def getMin(self):
return self.mins[-1]
def eval_rpn(tokens):
st = []
for s in tokens:
if s in ("+", "-", "*", "/"):
b = st.pop()
a = st.pop()
if s == "+": st.append(a + b)
elif s == "-": st.append(a - b)
elif s == "*": st.append(a * b)
else: st.append(int(a / b)) # truncate toward zero; a // b would floor
else:
st.append(int(s))
return st.pop()
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin()) # -3
ms.pop()
print(ms.top(), ms.getMin()) # 0 -2
print(eval_rpn("2 1 + 3 *".split())) # 9
print(eval_rpn("4 13 5 / +".split())) # 6
print(eval_rpn("10 6 9 3 + -11 * / * 17 + 5 +".split())) # 22
print(eval_rpn("7 -2 /".split())) # -3
print(7 // -2) # -4: the floor-division trap
Python's // floors (7 // -2 is -4), so use int(a / b) to truncate toward zero like Java and C++. (int(a / b) goes through a float, which is exact for 32-bit values like LeetCode's.)
Real bugs
Bug 1: getMin on an empty stack
push(4);
pop();
System.out.println(getMin());
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Deque.peek()" is null
peek() on an empty ArrayDeque returns null, and unboxing null into an int fails. LeetCode never calls getMin on an empty stack; real code should check isEmpty() or throw its own clear exception.
Bug 2: popping the operands in the wrong order
int a = st.pop(), b = st.pop();
4 13 5 / + prints 4 instead of 6: it computed 5 / 13 = 0, then 4 + 0. + and * don't care about order, so the bug hides until a - or / appears. The first pop is always b.
Bug 3: a malformed expression
System.out.println(evalRPN(T("3 +")));
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:592)
at Main.evalRPN(Main.java:16)
at Main.main(Main.java:25)
pop() on an empty ArrayDeque throws. For user input, check that the stack has at least two values before an operator and exactly one at the end.
Complexity
| Approach | Time | Extra space | Big input |
|---|---|---|---|
Min stack, scan on every getMin |
O(n) per getMin, O(n²) total |
O(1) | Time Limit Exceeded |
Min stack, one min variable |
O(1) | O(1) | wrong answer after popping the minimum |
Min stack, second stack mins |
O(1) every operation | O(n) | 180 ms |
| RPN, find first operator and splice | O(n²) | O(n) | Time Limit Exceeded |
| RPN, operand stack | O(n) | O(n) | 197 ms |
(The times include the JVM warming up and boxing Integers; the work itself is linear.) The RPN stack is O(n) in the worst case, like a lakh ones pushed before any +.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
One int min variable |
-3 after popping -3 |
a variable forgets the older minimum | a second stack mins (or pairs) |
getMin() on an empty stack |
NullPointerException: ... peek() is null |
peek() returns null, unboxing crashes |
check isEmpty() first |
Pushing to mins only when x < mins.top |
wrong min after popping a duplicate minimum | equal values need their own entry (or a count) | push on every push, or use <= |
a = pop(), then b = pop() |
4 instead of 6 |
the first pop is the right operand | int b = st.pop(), a = st.pop(); |
"3 +" (too few operands) |
java.util.NoSuchElementException |
pop() on an empty ArrayDeque throws |
check size() >= 2 for untrusted input |
Python a // b |
-4 for 7 / -2 |
// floors |
int(a / b) |
s.charAt(0) == '-' to detect an operator |
-11 treated as minus |
negative numbers start with - |
compare the whole token |
| Splicing the list | TLE on 2 lakh tokens | O(n²) | operand stack |
Mini project: a pocket calculator
Read an ordinary (infix) expression with spaces between tokens, such as 5 + ( 1 + 2 ) * 4 - 3, convert it to postfix with the shunting-yard algorithm (Practice 3), then evaluate it with evalRPN. For that input the postfix is 5 1 2 + 4 * + 3 - and the result is 14. Extension: also print the value of the minimum intermediate result using your min stack.
Practice
- Min stack with ONE stack of pairs
{value, minSoFar}.
Solution
static Deque<int[]> ps = new ArrayDeque<>();
static void push1(int x) { ps.push(new int[]{x, ps.isEmpty() ? x : Math.min(x, ps.peek()[1])}); }
static void pop1() { ps.pop(); }
static int getMin1() { return ps.peek()[1]; }
push -2, 0, -3 → getMin1() = -3; after pop1() → -2. Same O(1) time and O(n) space, one stack.
- Max stack:
getMax()in O(1).
Solution
Same idea with Math.max:
static Deque<Integer> st = new ArrayDeque<>(), maxs = new ArrayDeque<>();
static void push2(int x) { st.push(x); maxs.push(maxs.isEmpty() ? x : Math.max(x, maxs.peek())); }
static void pop2() { st.pop(); maxs.pop(); }
static int getMax() { return maxs.peek(); }
push 1, 5, 3 → 5; pop twice → 1.
- Convert infix
( 2 + 1 ) * 3to postfix.
Solution
The shunting-yard algorithm: numbers go straight to the output; an operator first pops operators of higher or equal precedence; ( is pushed; ) pops until (.
static int prec(String op) { return op.equals("+") || op.equals("-") ? 1 : 2; }
static String toPostfix(String infix) {
StringBuilder out = new StringBuilder();
Deque<String> ops = new ArrayDeque<>();
for (String t : infix.split(" ")) {
if (t.equals("(")) ops.push(t);
else if (t.equals(")")) {
while (!ops.peek().equals("(")) out.append(ops.pop()).append(' ');
ops.pop();
} else if ("+-*/".contains(t)) {
while (!ops.isEmpty() && !ops.peek().equals("(") && prec(ops.peek()) >= prec(t))
out.append(ops.pop()).append(' ');
ops.push(t);
} else out.append(t).append(' ');
}
while (!ops.isEmpty()) out.append(ops.pop()).append(' ');
return out.toString().trim();
}
( 2 + 1 ) * 3 → 2 1 + 3 *; 5 + ( 1 + 2 ) * 4 - 3 → 5 1 2 + 4 * + 3 -.
- Evaluate prefix (Polish) notation:
* + 2 1 3.
Solution
Scan from right to left; now the first pop is the left operand a.
static int evalPrefix(String expr) {
String[] t = expr.split(" ");
Deque<Integer> s = new ArrayDeque<>();
for (int i = t.length - 1; i >= 0; i--) {
String x = t[i];
if ("+-*/".contains(x)) {
int a = s.pop(), b = s.pop();
s.push(switch (x) { case "+" -> a + b; case "-" -> a - b; case "*" -> a * b; default -> a / b; });
} else s.push(Integer.parseInt(x));
}
return s.pop();
}
* + 2 1 3 → 9; - 10 / 9 3 → 7.
Quick quiz
System.out.println(evalRPN(T("5 1 2 + 4 * + 3 -")));
20121417
Answer
14. 1 2 + = 3; 3 4 * = 12; 5 12 + = 17; 17 3 - = 14. In infix it is 5 + (1 + 2) * 4 - 3. (Real output: 14.)
Interview questions
- Design a stack with
getMinin O(1). A second stack where each entry is the minimum of everything at or below it (or one stack of pairs). Pop both together. - Why doesn't one
minvariable work? After popping the minimum you need the previous minimum, and one variable has no history. - Can you do it with O(1) extra space? Yes: store encoded values (
2x - minwhenx < min) in alongstack and decode on pop. It is tricky and overflow-prone; the two-stack version is the expected answer. - What is reverse Polish notation and why do calculators and compilers like it? The operator comes after its operands; there are no brackets or precedence rules, and one left-to-right pass with a stack evaluates it.
- In RPN evaluation, which operand is popped first? The right one (
b), because it was pushed last. - How do you convert infix to postfix? Dijkstra's shunting-yard algorithm, with an operator stack and precedence rules.
- What is the time and space complexity of RPN evaluation? O(n) time, O(n) space in the worst case (all numbers before the operators).
- How does integer division behave? Java and C++ truncate toward zero (
7 / -2 = -3); Python's//floors (-4).
Glossary
| Term | Meaning |
|---|---|
| Stack | A pile where you add (push) and remove (pop) only at the top: last in, first out |
push / pop / top (peek) |
Add on top / remove the top / look at the top without removing it |
| Min stack | A stack that also returns its smallest value in O(1) |
| O(1), constant time | The work doesn't grow with the size of the input |
| Operand | A value an operator works on (a number here) |
| Operator | The action: +, -, *, / |
| Infix notation | The operator between its operands: (2 + 1) * 3 |
| Postfix / reverse Polish notation (RPN) | The operator after its operands: 2 1 + 3 * |
| Prefix / Polish notation | The operator before its operands: * + 2 1 3 |
| Token | One piece of the expression: a number or an operator |
| Truncate toward zero | Drop the fractional part: -3.5 → -3 |
| Shunting-yard algorithm | Converts infix to postfix with an operator stack |
ArrayDeque |
Java's double-ended queue; with push / pop / peek it is the recommended stack |
NullPointerException |
Using null as if it were an object, e.g. unboxing it into an int |
NoSuchElementException |
Asking an empty collection for an element, e.g. pop() on an empty ArrayDeque |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- Min stack: scanning on every
getMinis O(n) and times out; oneminvariable is wrong after a pop. A second stack of minimums, moved together with the main stack, makes every operation O(1) with O(n) extra space. - Reverse Polish notation puts the operator after its operands. Splicing the list is O(n²); one operand stack evaluates it in O(n): push numbers; for an operator, pop
b, thena, pusha op b. - Watch the operand order, truncating division, and empty-stack exceptions.
Next episode: Queues: a queue from two stacks, the circular queue.