Difficulty: MediumStack

Min Stack

Problem in Plain English

Design a stack that supports push, pop, top and getMin, with every operation running in constant time. Storing the running minimum alongside each entry makes the minimum query a plain top-of-stack read.

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class: MinStack() initializes the stack object, void push(int val) pushes val onto the stack, void pop() removes the top element, int top() returns the top element, and int getMin() retrieves the minimum element in the stack. Every method must run in $O(1)$ time.

The constructor and push/pop produce null in the operation-sequence output. top and getMin return integers. Empty-stack queries and pops are outside the valid input contract.

Constraints

-2^31 <= val <= 2^31 - 1
Methods pop, top and getMin are always called on non-empty stacks.
At most 3 * 10^4 calls are made to push, pop, top and getMin.

Examples

Example 1

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]

Push -2, 0, -3. getMin returns -3. After pop, top returns 0 and getMin returns -2.

Example 2

Input: ["MinStack","push","push","getMin"] [[],[1],[2],[]]
Output: [null,null,null,1]

Push 1, 2. The minimum of the stack is 1.

Example 3

Input: ["MinStack","push","top","getMin","pop","push","getMin"] [[],[2147483647],[],[],[],[-2147483648],[]]
Output: [null,null,2147483647,2147483647,null,null,-2147483648]

A one-element stack has the same top and minimum. After removing its only entry, pushing the smallest signed 32-bit value starts a fresh stack; no stale minimum survives.

Example 4

Input: ["MinStack","push","push","push","getMin","pop","getMin","pop","top","getMin"] [[],[-2],[-2],[0],[],[],[],[],[],[]]
Output: [null,null,null,null,-2,null,-2,null,-2,-2]

The minimum occurs twice. Popping 0 leaves both copies; popping the newer -2 still leaves the older -2. A single minimum flag without multiplicity or history would lose this information.

Intuition

A stack remembers values in last-in-first-out order, but its smallest value may be buried below the top. In Example 1, pushing -3 changes the minimum from -2 to -3; popping -3 must restore -2. Store a snapshot of the minimum with each entry, so removing the newest entry exposes the correct older snapshot. Duplicate minima need their own snapshots too.

Approaches

Rescan For Minimum

Solution Details

Reveal Rescan For Minimum: intuition, complexity, and code

Intuition

Store only the values and compute the minimum when requested. A full scan is a correct baseline because every live value is available, but it repeats work and does not meet the required constant-time getMin bound.

Step-by-Step Logic

Initialize an empty list. For every push(val), append val; Example 1 appends -2, 0, then -3, giving [-2, 0, -3].
For every getMin(), initialize a candidate from the first entry and scan all live entries, retaining the smaller of candidate and current value. The first query updates -2 -> -2 -> -3 and returns -3.
For pop(), remove only the last entry. Example 1 drops -3, leaving [-2, 0].
For top(), read the final entry without modifying the list; Example 1 returns 0.
Continue processing calls independently. The final minimum scan stays at -2; together with null outputs for construction and mutations, return [null,null,null,null,-3,null,0,-2].

Why It Works

After any operation, the list contains exactly the unpopped pushed values in insertion order: append adds the newest value, and removing the end undoes the latest surviving push. Thus its last value is the required top. During a minimum scan, after inspecting a prefix, the candidate is the minimum of that prefix; taking the smaller value extends this invariant by one entry. Once the entire list is inspected, the candidate is the minimum of all live entries. This is correct but not the required efficient implementation.

Dry Run

Rescan For Minimum: variable states at each step
Operation / scan step	Values bottom to top	Minimum candidate	Output so far
Constructor	[]	none	[null]
push(-2)	[-2]	none	[null,null]
push(0)	[-2,0]	none	[null,null,null]
push(-3)	[-2,0,-3]	none	[null,null,null,null]
getMin: initialize / inspect -2	[-2,0,-3]	-2	unchanged
getMin: inspect 0	[-2,0,-3]	min(-2,0) = -2	unchanged
getMin: inspect -3; return	[-2,0,-3]	min(-2,-3) = -3	[null,null,null,null,-3]
pop	[-2,0]	none	[null,null,null,null,-3,null]
top	[-2,0]	none	[null,null,null,null,-3,null,0]
getMin: initialize / inspect -2	[-2,0]	-2	unchanged
getMin: inspect 0; return	[-2,0]	min(-2,0) = -2	[null,null,null,null,-3,null,0,-2]

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the maximum number of live entries reached during a sequence of q calls. A getMin call scans the current depth, at most n; top and pop take O(1), and dynamic-array push takes amortized O(1), with O(n) worst-case resizing. The worst-case sequence costs O(qn), or O(q^2) when n grows with q. The list and its retained capacity use O(n) peak storage, with only O(1) extra scan state; Java/Python/JavaScript storage may retain capacity after pops. This baseline fails the constant-time minimum requirement.

Code

Solution.java

1import java.util.List;2import java.util.ArrayList;3
4class MinStack {5    private List<Integer> stack;6
7    public MinStack() {8        stack = new ArrayList<>();9    }10
11    public void push(int val) {12        stack.add(val);13    }14
15    public void pop() {16        stack.remove(stack.size() - 1);17    }18
19    public int top() {20        return stack.get(stack.size() - 1);21    }22
23    public int getMin() {24        int min = stack.get(0);25        for (int val : stack) {26            min = Math.min(min, val);27        }28        return min;29    }30}

Hints

Hint 1

A plain stack already handles push, pop and top in constant time, so only getMin needs a new idea.

Hint 2

The minimum after a pop is simply the minimum from before the matching push, which suggests remembering history.

Hint 3

Store each value together with the minimum of everything up to it, then answer getMin from the top entry.

Edge Cases

Pushing duplicate minimums such as [-2, 0, -2]: popping one copy must leave the other minimum intact.
Popping the unique minimum must reveal the previous higher minimum stored underneath.
Interleaved pushes and pops must keep every pair aligned, since each pop discards exactly one stored minimum.
Emptying and refilling the stack must discard the old minimum; queries on an empty stack are never required.
The extreme values -2147483648 and 2147483647 work using comparisons; arithmetic encodings based on 2 * val - min can overflow a Java int.

Common Mistakes and Interview Tips

Keeping a single global minimum variable, which breaks the moment the entry holding that minimum is popped.
Scanning the stack inside getMin, which is correct but costs linear time and violates the constant-time requirement.
Returning the stored minimum from top or the stored value from getMin by mixing up the two halves of the pair.
If using a separate minima stack, recording only strictly smaller minima loses duplicate counts; use <= or store counts. Per-entry snapshots avoid that bug.
Calling an array-backed push worst-case constant time ignores resizing. State amortized bounds explicitly, or use fixed-size linked nodes for constant work per method.

Key Takeaway

When a last-in-first-out structure must answer a running property in constant time, store that property alongside each entry so push and pop maintain it for free.