Definition
- Min Stack – a stack augmented with an O(1) getMin operation that returns the current minimum element.
- Two-stack design – a main stack for values and an auxiliary stack where each entry is the minimum of all elements up to that level.
- Push – push the value onto main; push
min(value, currentMin)onto the auxiliary stack. - Pop – pop both stacks together to maintain alignment.
- getMin – peek the auxiliary stack in O(1).
- Space – O(n) extra for the auxiliary stack; optimized variant pushes only new minimums.
Picture a clerk at the National Bank of India stacking account balance slips. Next to the main spike she keeps a second spike of "smallest so far" slips. Every time she adds a balance, she also adds a slip showing the smallest balance seen up to that point. When she removes the top balance, she removes the matching smallest slip too. At any instant she can glance at the second spike and know the smallest balance on the stack.
Understanding the Concepts
What is a Min Stack?
A Min Stack supports push, pop, top, and getMin, all in O(1) time. A plain stack would require scanning all elements to find the minimum, which is O(n). The trick is a second stack that tracks running minimums in lockstep with the main stack.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class MinStack {
private final Deque<Integer> main = new ArrayDeque<>();
private final Deque<Integer> mins = new ArrayDeque<>();
public void push(int val) {
main.push(val);
mins.push(mins.isEmpty() ? val : Math.min(val, mins.peek()));
}
public void pop() { main.pop(); mins.pop(); }
public int top() { return main.peek(); }
public int getMin() { return mins.peek(); }
public static void main(String[] args) {
MinStack ms = new MinStack();
ms.push(5); ms.push(3); ms.push(7); ms.push(2);
System.out.println("Min: " + ms.getMin());
ms.pop();
System.out.println("After pop: " + ms.getMin());
}
}
Min: 2
After pop: 3
Why does the two-stack approach work?
At each level the min stack entry records the smallest value among all elements from the bottom up to that point. Because the stacks are popped in lockstep, removing the top also removes its min record, and the new top is the correct minimum for whatever remains.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class MinStackInvariant {
public static void main(String[] args) {
Deque<Integer> main = new ArrayDeque<>();
Deque<Integer> mins = new ArrayDeque<>();
int[] vals = {5, 3, 7, 2, 8};
for (int v : vals) {
main.push(v);
mins.push(mins.isEmpty() ? v : Math.min(v, mins.peek()));
System.out.println("Push " + v + ": min=" + mins.peek());
}
while (!main.isEmpty()) {
System.out.println("Pop " + main.pop() + ": min=" + mins.pop());
}
}
}
Push 5: min=5
Push 3: min=3
Push 7: min=3
Push 2: min=2
Push 8: min=2
Pop 8: min=2
Pop 2: min=2
Pop 7: min=3
Pop 3: min=3
Pop 5: min=5
How do you implement it with BigDecimal for money?
Banking amounts use BigDecimal. Comparisons use compareTo rather than <. The logic is the same: push the smaller of the new value and the current min onto the auxiliary stack.
package com.bank.service;
import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.Deque;
public class MinStackMoney {
private final Deque<BigDecimal> main = new ArrayDeque<>();
private final Deque<BigDecimal> mins = new ArrayDeque<>();
public void push(BigDecimal val) {
main.push(val);
BigDecimal curMin = mins.isEmpty() ? val
: (val.compareTo(mins.peek()) <= 0 ? val : mins.peek());
mins.push(curMin);
}
public BigDecimal pop() { mins.pop(); return main.pop(); }
public BigDecimal getMin() { return mins.peek(); }
public static void main(String[] args) {
MinStackMoney ms = new MinStackMoney();
ms.push(new BigDecimal("50000.00"));
ms.push(new BigDecimal("30000.00"));
ms.push(new BigDecimal("75000.00"));
System.out.println("Lowest balance: " + ms.getMin());
}
}
Lowest balance: 30000.00
What is the space-optimized variant?
Push to the min stack only when the new value is less than or equal to the current minimum. Pop from the min stack only when the popped value equals the current minimum. Use <= not < so duplicate minimums are tracked correctly.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class MinStackOptimized {
private final Deque<Integer> main = new ArrayDeque<>();
private final Deque<Integer> mins = new ArrayDeque<>();
public void push(int val) {
main.push(val);
if (mins.isEmpty() || val <= mins.peek()) mins.push(val);
}
public void pop() {
if (main.pop().equals(mins.peek())) mins.pop();
}
public int getMin() { return mins.peek(); }
public static void main(String[] args) {
MinStackOptimized ms = new MinStackOptimized();
ms.push(3); ms.push(3); ms.push(5);
ms.pop(); // pop 5
System.out.println("Min: " + ms.getMin()); // 3
ms.pop(); // pop 3 (duplicate)
System.out.println("Min: " + ms.getMin()); // 3 (still correct)
}
}
Min: 3
Min: 3
Why does <= matter for duplicates?
With strict <, pushing the same minimum twice only creates one min entry. Popping one copy removes that entry, leaving the other copy with no min record. Using <= creates an entry for each copy, so popping one still leaves the other correctly tracked.
package com.bank.core;
public class DuplicateMinExplanation {
public static void main(String[] args) {
System.out.println("With <: push 3,3 -> mins=[3]. Pop 3 -> mins=[]. Bug!");
System.out.println("With <=: push 3,3 -> mins=[3,3]. Pop 3 -> mins=[3]. Correct.");
}
}
With <: push 3,3 -> mins=[3]. Pop 3 -> mins=[]. Bug!
With <=: push 3,3 -> mins=[3,3]. Pop 3 -> mins=[3]. Correct.
What are common mistakes?
Using strict < in the optimized variant is the subtlest bug. Forgetting to pop the min stack on pop is another. For the simple two-stack version, using int comparison on Integer objects beyond the cached -128..127 range can fail; using equals() or unboxing to int avoids this.
package com.bank.core;
public class MinStackMistakes {
public static void main(String[] args) {
System.out.println("Mistake 1: strict < in optimized variant -> duplicate min bug");
System.out.println("Mistake 2: forget to pop min stack on pop() -> drift");
System.out.println("Mistake 3: == on Integer objects > 127 -> wrong comparison");
System.out.println("Fix: use .equals() or unbox to int");
}
}
Mistake 1: strict < in optimized variant -> duplicate min bug
Mistake 2: forget to pop min stack on pop() -> drift
Mistake 3: == on Integer objects > 127 -> wrong comparison
Fix: use .equals() or unbox to int
How is this applied in banking?
At the National Bank of India, a risk dashboard tracks a customer's intraday balance as positions open and close. The desk constantly needs the lowest balance to check overdraft thresholds. The min stack answers that in O(1), and reversing a position by popping immediately surfaces the correct previous minimum.
package com.bank.service;
import java.math.BigDecimal;
public class RiskDashboard {
public static void main(String[] args) {
MinStackMoney tracker = new MinStackMoney();
tracker.push(new BigDecimal("100000.00"));
tracker.push(new BigDecimal("85000.00"));
tracker.push(new BigDecimal("120000.00"));
tracker.push(new BigDecimal("70000.00"));
System.out.println("Lowest intraday: " + tracker.getMin());
tracker.pop(); // reverse last position
System.out.println("After reversal: " + tracker.getMin());
}
}
Lowest intraday: 70000.00
After reversal: 85000.00
What should a senior engineer know?
Three approaches exist: two stacks in lockstep (O(n) extra, clearest), optimized push-only-on-new-min (less space, trickier pop), and delta encoding in a single stack (O(1) extra, hard to read). For interviews, present the clean two-stack version first and mention optimizations to show depth.
package com.bank.core;
public class MinStackApproaches {
public static void main(String[] args) {
System.out.println("1. Two stacks in lockstep: O(n) space, clear");
System.out.println("2. Push only on <=: less space, tricky pop");
System.out.println("3. Delta encoding: O(1) extra, hard to read");
System.out.println("Interview: present 1, mention 2 and 3");
}
}
1. Two stacks in lockstep: O(n) space, clear
2. Push only on <=: less space, tricky pop
3. Delta encoding: O(1) extra, hard to read
Interview: present 1, mention 2 and 3
Visual Overview
Two-Stack Min Stack ─────────────────── Push: 5, 3, 7, 2 Main Stack Min Stack ┌─────┐ ┌─────┐ │ 2 │ top │ 2 │ top ← getMin() ├─────┤ ├─────┤ │ 7 │ │ 3 │ ├─────┤ ├─────┤ │ 3 │ │ 3 │ ├─────┤ ├─────┤ │ 5 │ │ 5 │ └─────┘ └─────┘ pop() removes 2 from both: Main Stack Min Stack ┌─────┐ ┌─────┐ │ 7 │ top │ 3 │ top ← getMin() ├─────┤ ├─────┤ │ 3 │ │ 3 │ ├─────┤ ├─────┤ │ 5 │ │ 5 │ └─────┘ └─────┘
Key Takeaway
A Min Stack augments a normal stack with O(1) minimum retrieval by keeping a second auxiliary stack whose top always holds the current minimum. On push, I push the value onto the main stack and the smaller of the value and the current minimum onto the auxiliary. On pop, I pop both in lockstep. The getMin operation is a single peek.
The two-stack invariant is simple: at every level the auxiliary entry is the smallest value present from the bottom to that level. Popping in lockstep maintains this automatically. For banking money I use BigDecimal with compareTo rather than primitive operators to ensure correct scale and precision.
The space-optimized variant pushes to the min stack only on <= and pops only when the value matches the current minimum. The <= rather than < distinction is critical for handling duplicate minimums. A third approach encodes deltas in a single stack but sacrifices readability.
In my project at the National Bank of India, the risk dashboard tracks intraday balances as positions open and close, and the desk constantly needs the lowest balance for overdraft threshold checks. The min stack answers that in O(1) even as balances churn rapidly.
Remember one sentence: keep a parallel min stack in lockstep so the top is always the current minimum in O(1).
---