Definition
- Min Stack – a data-structure design problem that augments a normal stack with O(1) minimum retrieval.
- Two-stack approach – maintain a main stack for values and an auxiliary stack where each entry records the minimum of all elements present up to that level.
- Push rule – push the value onto the main stack and push
min(value, currentMin)onto the auxiliary stack. - Pop rule – pop both stacks together so they stay aligned and the minimum stays correct.
- getMin – peek the auxiliary stack in O(1); no scanning needed.
- Space trade-off – O(n) extra space for the auxiliary stack; an optimization pushes only new minimums.
Rajesh at the National Bank of India tracks account balances on a pile of slips. On top of each slip he also writes the lowest balance the account has ever had up to that point. When he removes the top slip, the lowest-ever note on the new top is still correct because it was recorded for that earlier state. At any instant he can glance at the top and know both the current balance and the lowest balance, without rereading the whole pile.
Understanding the Concepts
What is a Min Stack?
A Min Stack is a stack that supports push, pop, top, and getMin, all in O(1) time. A normal stack can do push, pop, and top in O(1), but finding the minimum requires scanning every element, which is O(n). The Min Stack eliminates that scan by keeping a second stack that tracks the running minimum.
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()); // 2
ms.pop();
System.out.println("Min after pop: " + ms.getMin()); // 3
}
}
Min: 2
Min after pop: 3
Why does the two-stack approach work?
The auxiliary stack mirrors the main stack element by element. At each level, the auxiliary entry is the smallest value among all elements from the bottom up to that level. Because the stacks are popped together, removing the top value also removes its minimum record, and the new top of the auxiliary stack is the correct minimum for the remaining elements.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class TwoStackInvariant {
public static void main(String[] args) {
Deque<Integer> main = new ArrayDeque<>();
Deque<Integer> mins = new ArrayDeque<>();
int[] values = {5, 3, 7, 2, 8};
for (int v : values) {
main.push(v);
mins.push(mins.isEmpty() ? v : Math.min(v, mins.peek()));
System.out.println("Push " + v + " -> main top=" + main.peek() + ", min top=" + mins.peek());
}
System.out.println("\nPopping:");
while (!main.isEmpty()) {
System.out.println("Pop " + main.pop() + " -> min=" + (mins.pop()) +
(mins.isEmpty() ? " (empty)" : ", next min=" + mins.peek()));
}
}
}
Push 5 -> main top=5, min top=5
Push 3 -> main top=3, min top=3
Push 7 -> main top=7, min top=3
Push 2 -> main top=2, min top=2
Push 8 -> main top=8, min top=2
Popping:
Pop 8 -> min=2, next min=2
Pop 2 -> min=2, next min=3
Pop 7 -> min=3, next min=3
Pop 3 -> min=3, next min=5
Pop 5 -> min=5 (empty)
How do you implement it with BigDecimal for banking?
Money must use BigDecimal, never double. Comparisons use compareTo rather than the < operator. The logic is the same: push the smaller of the new value and the current minimum onto the auxiliary stack.
package com.bank.service;
import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.Deque;
public class MinStackBigDecimal {
private final Deque<BigDecimal> main = new ArrayDeque<>();
private final Deque<BigDecimal> mins = new ArrayDeque<>();
public void push(BigDecimal val) {
main.push(val);
BigDecimal currentMin = mins.isEmpty() ? val
: (val.compareTo(mins.peek()) <= 0 ? val : mins.peek());
mins.push(currentMin);
}
public BigDecimal pop() { mins.pop(); return main.pop(); }
public BigDecimal top() { return main.peek(); }
public BigDecimal getMin() { return mins.peek(); }
public static void main(String[] args) {
MinStackBigDecimal ms = new MinStackBigDecimal();
ms.push(new BigDecimal("50000.00"));
ms.push(new BigDecimal("30000.00"));
ms.push(new BigDecimal("75000.00"));
ms.push(new BigDecimal("20000.00"));
System.out.println("Lowest balance: " + ms.getMin());
ms.pop();
System.out.println("After removing 20000: " + ms.getMin());
}
}
Lowest balance: 20000.00
After removing 20000: 30000.00
What is the space-optimized variant?
Instead of storing a minimum at every level, push onto 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 main value equals the current minimum. This saves space when minimums repeat rarely.
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() {
int val = main.pop();
if (val == mins.peek()) {
mins.pop();
}
}
public int top() { return main.peek(); }
public int getMin() { return mins.peek(); }
public static void main(String[] args) {
MinStackOptimized ms = new MinStackOptimized();
ms.push(5); ms.push(3); ms.push(7); ms.push(3); ms.push(2);
System.out.println("Min: " + ms.getMin()); // 2
ms.pop(); // remove 2
System.out.println("Min: " + ms.getMin()); // 3
ms.pop(); // remove 3 (duplicate min)
System.out.println("Min: " + ms.getMin()); // 3 (still correct)
}
}
Min: 2
Min: 3
Min: 3
Why does less-than-or-equal matter for duplicates?
If you use strict less-than when pushing to the min stack, duplicate minimums are not tracked. When one copy is popped, the min stack entry is removed, but the other copy still exists in the main stack with no matching min entry. Using less-than-or-equal ensures every copy of the minimum gets its own min stack entry.
package com.bank.core;
public class DuplicateMinBug {
public static void main(String[] args) {
// If we push 3 twice but only track min on strict <:
// main: [3, 7, 3, 5] mins: [3]
// Pop 3 from main -> mins pops 3 -> mins empty!
// But 3 still exists in main -> getMin() crashes
System.out.println("Using strict < : duplicate min causes incorrect behavior");
System.out.println("Using <= : both copies of 3 are tracked in min stack");
System.out.println("Always use <= in the optimized variant");
}
}
Using strict < : duplicate min causes incorrect behavior
Using <= : both copies of 3 are tracked in min stack
Always use <= in the optimized variant
What are the edge cases?
Pushing a single element makes it both the top and the minimum. Pushing identical values should keep the minimum correct after any number of pops. Pushing values in decreasing order means every value is a new minimum, so the min stack grows to the same size as the main stack.
package com.bank.service;
public class MinStackEdgeCases {
public static void main(String[] args) {
MinStack ms = new MinStack();
ms.push(42);
System.out.println("Single element min: " + ms.getMin()); // 42
MinStack ms2 = new MinStack();
ms2.push(5); ms2.push(5); ms2.push(5);
ms2.pop();
System.out.println("Duplicates min after pop: " + ms2.getMin()); // 5
MinStack ms3 = new MinStack();
ms3.push(3); ms3.push(2); ms3.push(1);
System.out.println("Decreasing min: " + ms3.getMin()); // 1
}
}
Single element min: 42
Duplicates min after pop: 5
Decreasing min: 1
How is this applied in banking?
At the National Bank of India, the risk dashboard tracks a customer's intraday balance as positions open and close. The desk constantly asks for the lowest balance to check overdraft thresholds. The auxiliary min stack answers that in O(1), and when a position is reversed, popping both stacks immediately surfaces the correct previous minimum without rescanning.
package com.bank.service;
import java.math.BigDecimal;
public class RiskDashboard {
public static void main(String[] args) {
MinStackBigDecimal tracker = new MinStackBigDecimal();
tracker.push(new BigDecimal("100000.00")); // opening
tracker.push(new BigDecimal("85000.00")); // withdrawal
tracker.push(new BigDecimal("120000.00")); // deposit
tracker.push(new BigDecimal("70000.00")); // large withdrawal
System.out.println("Lowest intraday balance: " + tracker.getMin());
tracker.pop(); // reverse last position
System.out.println("After reversal: " + tracker.getMin());
}
}
Lowest intraday balance: 70000.00
After reversal: 85000.00
What should a senior engineer know?
The two-stack approach uses O(n) extra space. The space-optimized variant reduces this when few values are minimums, but adds complexity to the pop logic. A third approach stores deltas from the minimum in a single stack, encoding the minimum change in the stored value, trading clarity for space. For interviews, present the clean two-stack version first and mention optimizations to show depth. All variants keep every operation O(1).
package com.bank.core;
public class MinStackSummary {
public static void main(String[] args) {
System.out.println("Approach 1: Two stacks in lockstep - O(n) extra space, clear logic");
System.out.println("Approach 2: Push to min only on <= - less space, trickier pop");
System.out.println("Approach 3: Delta encoding - O(1) extra space, hard to read");
System.out.println("Interview default: Approach 1, mention 2 and 3 for depth");
}
}
Approach 1: Two stacks in lockstep - O(n) extra space, clear logic
Approach 2: Push to min only on <= - less space, trickier pop
Approach 3: Delta encoding - O(1) extra space, hard to read
Interview default: Approach 1, mention 2 and 3 for depth
Visual Overview
Two-Stack Min Stack Invariant ───────────────────────────── Push sequence: 5, 3, 7, 2 Main Stack Min Stack ┌─────┐ ┌─────┐ │ 2 │ top │ 2 │ top ← getMin() = 2 ├─────┤ ├─────┤ │ 7 │ │ 3 │ ├─────┤ ├─────┤ │ 3 │ │ 3 │ ├─────┤ ├─────┤ │ 5 │ │ 5 │ └─────┘ └─────┘ After pop(): Main Stack Min Stack ┌─────┐ ┌─────┐ │ 7 │ top │ 3 │ top ← getMin() = 3 ├─────┤ ├─────┤ │ 3 │ │ 3 │ ├─────┤ ├─────┤ │ 5 │ │ 5 │ └─────┘ └─────┘
Key Takeaway
A Min Stack augments a normal stack with an O(1) getMin operation by keeping a second auxiliary stack whose top always holds the current minimum. On every push, I push the value onto the main stack and push the smaller of the new value and the current minimum onto the auxiliary stack. On every pop, I pop both stacks together so the minimum stays correct as elements are removed. The getMin operation is a single peek on the auxiliary stack.
The elegance is in the invariant: at every level, the auxiliary stack entry is the smallest value among all elements from the bottom up to that level. Because the stacks are popped in lockstep, removing the top value also removes its minimum record, and the new top of the auxiliary stack is automatically the correct minimum for whatever remains.
For banking money, I use BigDecimal rather than primitives and compare with compareTo instead of the < operator, because money comparisons must respect scale and precision. There is a space-optimized variant that pushes to the min stack only when a value is less than or equal to the current minimum, but the key detail is using less-than-or-equal rather than strict less-than so that duplicate minimums are tracked correctly.
In my project at the National Bank of India, I used this inside a risk monitor that tracks a customer's intraday balance as positions open and close. The desk constantly asks for the lowest balance to check overdraft thresholds, and the auxiliary min stack answers that in O(1) even as balances churn rapidly. When a position is reversed, popping both stacks immediately surfaces the correct previous minimum without any rescan.
Remember one sentence: keep a parallel min stack in lockstep with the main stack so the top of the min stack is always the current minimum in O(1).
---