DSA-042 · A minimum snapshot at every linked stack node
Min Stack
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 82147 deterministic checks. Learner drafts are not executed.
Understand the problem
Implement a stack that supports push, returning pop, top, minimum, and size in constant pointer work per operation.
- Use Solution.MinStack with push(int) returning void, pop() returning the removed int, top(), getMin(), and size(). Values may be any signed int, including both extremes and repeated minima. A sequence contains at most 100,000 operations/live entries under this teaching contract.
- pop, top, and getMin throw NoSuchElementException on empty without changing the state; size returns zero on empty. Each new instance starts empty and owns its state.
- The optimized linked node stores its own value, the minimum of itself and the nodes below it, and the next reference. It uses no subtraction-based encoding, numeric sentinel, global mutable minimum, or shared static stack. Trace outcomes use null for void push and an exception-name string for a thrown operation.
Examples
Input:
push(3), push(1), push(1), pop(), getMin()
Output:pop returns 1; minimum remains 1The remaining equal minimum belongs to its own saved node.
Input:
push(-2147483648), push(2147483647), getMin()
Output:-2147483648Comparisons handle extremes without arithmetic encoding.
Before you start
- Stack top versus bottom and last-in-first-out order
- Loop invariants, checked arithmetic, and amortized analysis
Recognize the structure
A pop must restore the minimum of an earlier stack version. Saving that aggregate with every node makes restoration a pointer change instead of a rescan or a fragile attempt to reconstruct a destroyed minimum.
Try before revealing
Hint 1
What information must reappear when the top node is removed?
Hint 2
Can every node save the minimum of its own remaining suffix?
Hint 3
Push a value/minimum/next node; pop restores the old head.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Store values and scan for a minimum
An ArrayList holds values in stack order. top/pop use the final element, while getMin scans all values. On [3,1,1,2], getMin is one; after popping 2 and then 1 it is still one. A scan is correct but costs O(n) per minimum query, motivating a saved aggregate at each level.
Improve the baseline
Define a node aggregate
For a pushed value x above old minimum m, the new minimum is min(x,m); for the first value it is x.
Link a new version
Create an immutable node with value, aggregate, and old head as next. Set head to it and increment size.
Restore by following next
Pop saves head.value, moves head to head.next, and decrements size. The new head already contains the correct previous minimum, including duplicates.
Why it is correct
Node invariant
At every node, minimum equals the minimum of all values from that node through the bottom. The first node satisfies this immediately; adding x with min(x,oldMinimum) preserves it inductively.
Push/pop preservation
A push does not change old nodes. A pop removes only the head, exposing an unchanged suffix whose aggregate is already correct. Duplicate minima require no special case because each occurrence owns a node.
Observations and empty state
top and getMin read the head’s value and aggregate. size tracks the number of reachable nodes through one increment/decrement per successful mutation. Empty checks throw before any mutation, so failed reads/pops preserve the empty state.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.ArrayList;
import java.util.NoSuchElementException;
public final class Solution {
public static final class MinStack {
private static final class Node {
final int value, minimum;
final Node next;
Node(int value, int minimum, Node next) { this.value = value; this.minimum = minimum; this.next = next; }
}
private Node head;
private int size;
public void push(int value) {
head = new Node(value, head == null ? value : Math.min(value, head.minimum), head);
size++;
}
public int pop() {
if (head == null) throw new NoSuchElementException("empty stack");
int value = head.value;
head = head.next;
size--;
return value;
}
public int top() {
if (head == null) throw new NoSuchElementException("empty stack");
return head.value;
}
public int getMin() {
if (head == null) throw new NoSuchElementException("empty stack");
return head.minimum;
}
public int size() { return size; }
}
public static final class Baseline {
private final ArrayList<Integer> values = new ArrayList<>();
public void push(int value) { values.add(value); }
public int pop() { if (values.isEmpty()) throw new NoSuchElementException("empty stack"); return values.removeLast(); }
public int top() { if (values.isEmpty()) throw new NoSuchElementException("empty stack"); return values.getLast(); }
public int getMin() {
if (values.isEmpty()) throw new NoSuchElementException("empty stack");
int minimum = Integer.MAX_VALUE;
for (int value : values) minimum = Math.min(minimum, value);
return minimum;
}
public int size() { return values.size(); }
}
}
Read the meaningful blocks
Immutable node fields
Saved values and minima cannot be accidentally changed when later pushes occur.
No encoded differences
Math.min compares ints directly. A difference between Integer.MIN_VALUE and Integer.MAX_VALUE would not fit int.
Explicit empty checks
An empty stack has no numeric minimum; neither zero nor Integer.MAX_VALUE is a safe absent-value sentinel when those are valid values.
Complexity
Each optimized operation performs O(1) pointer/comparison work and allocates at most one node; allocator/GC costs are outside the usual data-structure model. With n live entries, storage is O(n).
The ArrayList baseline has amortized O(1) push, O(1) end pop/top/size, and O(n) getMin. It also uses O(n) storage. A dynamic-array implementation of the optimized pair idea would give amortized rather than worst-case pointer-work push.
Exact-state walkthroughs
Reveal normal and boundary traces
Duplicate minima restore at each pop
Input: {"operations":[["push",3],["push",1],["push",1],["push",2],["getMin"],["pop"],["pop"],["getMin"],["pop"],["getMin"]]} · Operation outcomes: [null,null,null,null,1,2,1,1,1,3]
Step 1 of 12: Initialize a new linked MinStack.
The display is bottom to top. Each saved minimum belongs to that node and the nodes below it.
Empty at this step.
| Variable | Value |
|---|---|
| stackValues | [] |
| savedMinima | [] |
| size | 0 |
| outcomes | [] |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.NoSuchElementException; 3 public final class Solution { 4 public static final class MinStack { 5 private static final class Node { 6 final int value, minimum; 7 final Node next; 8 Node(int value, int minimum, Node next) { this.value = value; this.minimum = minimum; this.next = next; } 9 } 10 private Node head; 11 private int size; 12 public void push(int value) { 13 head = new Node(value, head == null ? value : Math.min(value, head.minimum), head); 14 size++; 15 } 16 public int pop() { 17 if (head == null) throw new NoSuchElementException("empty stack"); 18 int value = head.value; 19 head = head.next; 20 size--; 21 return value; 22 } 23 public int top() { 24 if (head == null) throw new NoSuchElementException("empty stack"); 25 return head.value; 26 } 27 public int getMin() { 28 if (head == null) throw new NoSuchElementException("empty stack"); 29 return head.minimum; 30 } 31 public int size() { return size; } 32 } 33 public static final class Baseline { 34 private final ArrayList<Integer> values = new ArrayList<>(); 35 public void push(int value) { values.add(value); } 36 public int pop() { if (values.isEmpty()) throw new NoSuchElementException("empty stack"); return values.removeLast(); } 37 public int top() { if (values.isEmpty()) throw new NoSuchElementException("empty stack"); return values.getLast(); } 38 public int getMin() { 39 if (values.isEmpty()) throw new NoSuchElementException("empty stack"); 40 int minimum = Integer.MAX_VALUE; 41 for (int value : values) minimum = Math.min(minimum, value); 42 return minimum; 43 } 44 public int size() { return values.size(); } 45 } 46 } 47
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize a new linked MinStack.
The display is bottom to top. Each saved minimum belongs to that node and the nodes below it.
- stackValues
[]- savedMinima
[]- size
0- outcomes
[]
- Apply push and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
0- operation
"push"- value
3- outcome
null- stackValues
[3]- savedMinima
[3]- size
1- outcomes
[null]
- Apply push and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
1- operation
"push"- value
1- outcome
null- stackValues
[3,1]- savedMinima
[3,1]- size
2- outcomes
[null,null]
- Apply push and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
2- operation
"push"- value
1- outcome
null- stackValues
[3,1,1]- savedMinima
[3,1,1]- size
3- outcomes
[null,null,null]
- Apply push and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
3- operation
"push"- value
2- outcome
null- stackValues
[3,1,1,2]- savedMinima
[3,1,1,1]- size
4- outcomes
[null,null,null,null]
- Apply getMin and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
4- operation
"getMin"- outcome
1- stackValues
[3,1,1,2]- savedMinima
[3,1,1,1]- size
4- outcomes
[null,null,null,null,1]
- Apply pop and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
5- operation
"pop"- outcome
2- stackValues
[3,1,1]- savedMinima
[3,1,1]- size
3- outcomes
[null,null,null,null,1,2]
- Apply pop and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
6- operation
"pop"- outcome
1- stackValues
[3,1]- savedMinima
[3,1]- size
2- outcomes
[null,null,null,null,1,2,1]
- Apply getMin and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
7- operation
"getMin"- outcome
1- stackValues
[3,1]- savedMinima
[3,1]- size
2- outcomes
[null,null,null,null,1,2,1,1]
- Apply pop and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
8- operation
"pop"- outcome
1- stackValues
[3]- savedMinima
[3]- size
1- outcomes
[null,null,null,null,1,2,1,1,1]
- Apply getMin and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
9- operation
"getMin"- outcome
3- stackValues
[3]- savedMinima
[3]- size
1- outcomes
[null,null,null,null,1,2,1,1,1,3]
- Complete the operation sequence; labels include void and thrown outcomes.
The completed result follows the declared ordering, empty-state, and numeric semantics.
- result
[null,null,null,null,1,2,1,1,1,3]
Empty operations and full int bounds
Input: {"operations":[["top"],["push",-2147483648],["push",2147483647],["getMin"],["pop"],["pop"],["getMin"],["size"]]} · Operation outcomes: ["NoSuchElementException",null,null,-2147483648,2147483647,-2147483648,"NoSuchElementException",0]
Step 1 of 10: Initialize a new linked MinStack.
The display is bottom to top. Each saved minimum belongs to that node and the nodes below it.
Empty at this step.
| Variable | Value |
|---|---|
| stackValues | [] |
| savedMinima | [] |
| size | 0 |
| outcomes | [] |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.NoSuchElementException; 3 public final class Solution { 4 public static final class MinStack { 5 private static final class Node { 6 final int value, minimum; 7 final Node next; 8 Node(int value, int minimum, Node next) { this.value = value; this.minimum = minimum; this.next = next; } 9 } 10 private Node head; 11 private int size; 12 public void push(int value) { 13 head = new Node(value, head == null ? value : Math.min(value, head.minimum), head); 14 size++; 15 } 16 public int pop() { 17 if (head == null) throw new NoSuchElementException("empty stack"); 18 int value = head.value; 19 head = head.next; 20 size--; 21 return value; 22 } 23 public int top() { 24 if (head == null) throw new NoSuchElementException("empty stack"); 25 return head.value; 26 } 27 public int getMin() { 28 if (head == null) throw new NoSuchElementException("empty stack"); 29 return head.minimum; 30 } 31 public int size() { return size; } 32 } 33 public static final class Baseline { 34 private final ArrayList<Integer> values = new ArrayList<>(); 35 public void push(int value) { values.add(value); } 36 public int pop() { if (values.isEmpty()) throw new NoSuchElementException("empty stack"); return values.removeLast(); } 37 public int top() { if (values.isEmpty()) throw new NoSuchElementException("empty stack"); return values.getLast(); } 38 public int getMin() { 39 if (values.isEmpty()) throw new NoSuchElementException("empty stack"); 40 int minimum = Integer.MAX_VALUE; 41 for (int value : values) minimum = Math.min(minimum, value); 42 return minimum; 43 } 44 public int size() { return values.size(); } 45 } 46 } 47
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize a new linked MinStack.
The display is bottom to top. Each saved minimum belongs to that node and the nodes below it.
- stackValues
[]- savedMinima
[]- size
0- outcomes
[]
- Apply top and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
0- operation
"top"- outcome
"NoSuchElementException"- stackValues
[]- savedMinima
[]- size
0- outcomes
["NoSuchElementException"]
- Apply push and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
1- operation
"push"- value
-2147483648- outcome
null- stackValues
[-2147483648]- savedMinima
[-2147483648]- size
1- outcomes
["NoSuchElementException",null]
- Apply push and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
2- operation
"push"- value
2147483647- outcome
null- stackValues
[-2147483648,2147483647]- savedMinima
[-2147483648,-2147483648]- size
2- outcomes
["NoSuchElementException",null,null]
- Apply getMin and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
3- operation
"getMin"- outcome
-2147483648- stackValues
[-2147483648,2147483647]- savedMinima
[-2147483648,-2147483648]- size
2- outcomes
["NoSuchElementException",null,null,-2147483648]
- Apply pop and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
4- operation
"pop"- outcome
2147483647- stackValues
[-2147483648]- savedMinima
[-2147483648]- size
1- outcomes
["NoSuchElementException",null,null,-2147483648,2147483647]
- Apply pop and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
5- operation
"pop"- outcome
-2147483648- stackValues
[]- savedMinima
[]- size
0- outcomes
["NoSuchElementException",null,null,-2147483648,2147483647,-2147483648]
- Apply getMin and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
6- operation
"getMin"- outcome
"NoSuchElementException"- stackValues
[]- savedMinima
[]- size
0- outcomes
["NoSuchElementException",null,null,-2147483648,2147483647,-2147483648,"NoSuchElementException"]
- Apply size and preserve the saved suffix aggregate.
Every saved minimum is exact for its node suffix. null means a void push; the exception label means a thrown empty operation with unchanged state.
- index
7- operation
"size"- outcome
0- stackValues
[]- savedMinima
[]- size
0- outcomes
["NoSuchElementException",null,null,-2147483648,2147483647,-2147483648,"NoSuchElementException",0]
- Complete the operation sequence; labels include void and thrown outcomes.
The completed result follows the declared ordering, empty-state, and numeric semantics.
- result
["NoSuchElementException",null,null,-2147483648,2147483647,-2147483648,"NoSuchElementException",0]
Test the contract
Input:
new stack; size()
Output:0Independent empty instance.
Input:
new stack; getMin()
Output:NoSuchElementExceptionNo numeric sentinel.
Input:
push(1), push(1), pop(), getMin()
Output:1Duplicate minimum survives.
Input:
push(3), push(1), pop(), getMin()
Output:3Previous aggregate is restored.
Common mistakes and counterexamples
Save a minimum only when it strictly decreases
Counterexample: Pushing 1,1 and popping once must still report one.
Store an aggregate per node or count duplicate minima explicitly.
Keep only one mutable global minimum
Counterexample: After popping the unique minimum, the next minimum cannot be recovered from that one value.
Restore the saved minimum in the next node.
Encode arithmetic in int without proof
Counterexample: MAX_VALUE-MIN_VALUE exceeds int range.
Use direct comparisons and separate fields, or widen and prove every encoded bound.
Follow-ups
Add a maximum query.
Store both min and max aggregates per node. Constant extra fields preserve O(1) operation work and O(n) total storage.
Use arithmetic encoding.
Specify the encoded numeric domain and prove every intermediate fits. With full int values, widening to long can support some encodings, but empty behavior and duplicate restoration still need a precise invariant.
Test arbitrary operation sequences.
Maintain a plain list as the model, compare size/top/min after every mutation, and exercise empty operations between drains. Stateful tests catch restoration defects that isolated push/getMin examples miss.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 363/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.