Definition
- Min Stack – a stack supporting push, pop, top, and getMin, all in O(1) time.
- Auxiliary stack – mirrors the main stack; each entry records the minimum of all elements from the bottom to that level.
- Push – push value to main; push
min(value, mins.peek())to auxiliary. - Pop – pop both stacks together.
- getMin – peek the auxiliary stack.
- Space – O(n) extra; optimized variant pushes only new minimums with
<=.
At the National Bank of India, the manager stacks deposit slips and must instantly answer "what is the smallest deposit still in this pile?" A clerk keeps a shadow pile where each slip records the smallest amount seen up to that point. When a slip is removed from the real pile, the matching shadow slip is removed too, so the top of the shadow pile is always the current smallest.
Understanding the Concepts
What is a Min Stack?
A stack that supports push, pop, top, and getMin in O(1). A plain stack would need O(n) to scan for the minimum. The two-stack approach trades O(n) extra space for O(1) getMin.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class MinStackO1 {
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) {
MinStackO1 ms = new MinStackO1();
ms.push(5); ms.push(1); ms.push(7);
System.out.println("Min: " + ms.getMin()); // 1
ms.pop(); // pop 7
System.out.println("Min: " + ms.getMin()); // 1
ms.pop(); // pop 1
System.out.println("Min: " + ms.getMin()); // 5
}
}
Min: 1
Min: 1
Min: 5
How does lockstep popping maintain correctness?
At each level, the auxiliary entry is the minimum of everything below and including that level. Popping both stacks removes the latest entry and reveals the previous minimum, which was correct for the earlier state. No recomputation is needed.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class LockstepDemo {
public static void main(String[] args) {
Deque<Integer> main = new ArrayDeque<>();
Deque<Integer> mins = new ArrayDeque<>();
int[] vals = {10, 3, 8, 1};
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());
}
System.out.println();
while (!main.isEmpty()) {
int v = main.pop();
int m = mins.pop();
System.out.println("Pop " + v + " -> previous min=" + (mins.isEmpty() ? "empty" : mins.peek()));
}
}
}
Push 10 -> min=10
Push 3 -> min=3
Push 8 -> min=3
Push 1 -> min=1
Pop 1 -> previous min=3
Pop 8 -> previous min=3
Pop 3 -> previous min=10
Pop 10 -> previous min=empty
How do you use BigDecimal for banking?
Money comparisons use compareTo. Push the smaller of the new value and the current minimum onto the auxiliary stack using <= 0 for the comparison.
package com.bank.service;
import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.Deque;
public class MinStackBD {
private final Deque<BigDecimal> main = new ArrayDeque<>();
private final Deque<BigDecimal> mins = new ArrayDeque<>();
public void push(BigDecimal val) {
main.push(val);
BigDecimal cur = mins.isEmpty() ? val
: (val.compareTo(mins.peek()) <= 0 ? val : mins.peek());
mins.push(cur);
}
public BigDecimal getMin() { return mins.peek(); }
public void pop() { main.pop(); mins.pop(); }
public static void main(String[] args) {
MinStackBD ms = new MinStackBD();
ms.push(new BigDecimal("50000"));
ms.push(new BigDecimal("30000"));
ms.push(new BigDecimal("80000"));
System.out.println("Lowest: " + ms.getMin());
}
}
Lowest: 30000
What is the space-optimized variant?
Push to the min stack only when val <= mins.peek(). Pop from it only when main.pop().equals(mins.peek()). Using <= ensures duplicate minimums are each tracked.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class MinStackOpt {
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) {
MinStackOpt ms = new MinStackOpt();
ms.push(3); ms.push(3); ms.push(5);
ms.pop();
System.out.println("Min: " + ms.getMin()); // 3
ms.pop();
System.out.println("Min: " + ms.getMin()); // 3
}
}
Min: 3
Min: 3
Why does <= matter for duplicate minimums?
Strict < creates only one min entry for duplicate minimums. Popping one copy removes that entry, leaving the other copy without a matching min record. The <= condition creates an entry per copy.
package com.bank.core;
public class DuplicateMinBug {
public static void main(String[] args) {
System.out.println("< : push 3,3 -> mins=[3]. Pop 3 -> mins=[]. Bug for second 3!");
System.out.println("<= : push 3,3 -> mins=[3,3]. Pop 3 -> mins=[3]. Correct!");
}
}
< : push 3,3 -> mins=[3]. Pop 3 -> mins=[]. Bug for second 3!
<= : push 3,3 -> mins=[3,3]. Pop 3 -> mins=[3]. Correct!
What are common mistakes?
Using < instead of <= in the optimized variant. Forgetting to pop both stacks in the simple version. Using == on Integer objects beyond the cached range. Not handling the empty-stack case on the first push.
package com.bank.core;
public class MinStackBugs {
public static void main(String[] args) {
System.out.println("Bug 1: strict < in optimized -> duplicate min lost");
System.out.println("Bug 2: pop only main, forget mins -> drift");
System.out.println("Bug 3: == on Integer > 127 -> reference comparison fails");
System.out.println("Bug 4: peek empty mins on first push -> exception");
}
}
Bug 1: strict < in optimized -> duplicate min lost
Bug 2: pop only main, forget mins -> drift
Bug 3: == on Integer > 127 -> reference comparison fails
Bug 4: peek empty mins on first push -> exception
How is this applied in banking?
At National Bank of India, the trading desk stages and cancels pending order amounts on a stack, and the risk monitor needs the smallest pending amount at every instant to enforce a floor rule. The min stack answers in O(1) even as orders churn rapidly.
package com.bank.service;
import java.math.BigDecimal;
public class TradingRiskMonitor {
public static void main(String[] args) {
MinStackBD desk = new MinStackBD();
desk.push(new BigDecimal("100000"));
desk.push(new BigDecimal("50000"));
desk.push(new BigDecimal("75000"));
System.out.println("Smallest pending: " + desk.getMin());
desk.pop();
System.out.println("After cancel: " + desk.getMin());
}
}
Smallest pending: 50000
After cancel: 50000
What should a senior engineer know?
Three approaches: two stacks in lockstep (O(n) space, clear), push-only-on-new-min (less space, tricky pop), and delta encoding (O(1) extra, hard to read). Present the clean two-stack version in interviews and mention the others to show depth.
package com.bank.core;
public class MinStackSenior {
public static void main(String[] args) {
System.out.println("1. Two stacks lockstep: O(n) extra, clear");
System.out.println("2. Push on <=: less space, tricky pop logic");
System.out.println("3. Delta encoding: O(1) extra, sacrifices clarity");
System.out.println("All keep every operation O(1)");
}
}
1. Two stacks lockstep: O(n) extra, clear
2. Push on <=: less space, tricky pop logic
3. Delta encoding: O(1) extra, sacrifices clarity
All keep every operation O(1)
Visual Overview
Two-Stack Min Stack ─────────────────── Push: 5, 1, 7 Main Stack Min Stack ┌─────┐ ┌─────┐ │ 7 │ top │ 1 │ top ← getMin() ├─────┤ ├─────┤ │ 1 │ │ 1 │ ├─────┤ ├─────┤ │ 5 │ │ 5 │ └─────┘ └─────┘ pop(7): both stacks pop Main: [1,5] Min: [1,5] → getMin()=1 pop(1): both stacks pop Main: [5] Min: [5] → getMin()=5
Key Takeaway
A Min Stack supports push, pop, top, and getMin all in O(1) by keeping a second auxiliary stack whose top always holds the current minimum. On every push, I push the value to main and the smaller of the value and the current minimum to the auxiliary. On every pop, I pop both in lockstep. The getMin operation is a single peek.
The invariant is that 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 to ensure correct scale and precision.
The space-optimized variant pushes to the min stack only when the value is <= the current minimum, and pops only when the removed value equals the minimum. The <= vs < distinction is critical: strict < fails to track duplicate minimums. A third approach encodes deltas in a single stack but trades clarity for O(1) extra space.
In my project at the National Bank of India, the trading desk stages pending orders on a stack and the risk monitor queries the smallest pending amount at every instant. The min stack answers in O(1) regardless of how rapidly orders churn.
Remember one sentence: keep a parallel min stack in lockstep so getMin is always a single peek in O(1).
---