Min Stack Design in DSA Java

Mental Model

A Min Stack keeps track of the smallest value at every point so you can get the minimum quickly.

Analogy: Imagine a stack of plates where each plate has a note showing the smallest plate size below it, so you always know the smallest plate without checking all plates.

Top -> [value: 3, min: 1] -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Dry Run Walkthrough

Input: Operations: push(5), push(1), push(3), getMin(), pop(), getMin()

Goal: Show how the stack updates and how getMin returns the smallest value quickly

Step 1: push 5 onto stack; min is 5

Top -> [value: 5, min: 5] -> null

Why: First element sets the minimum to itself

Step 2: push 1 onto stack; min updates to 1

Top -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: New value 1 is smaller than previous min 5, so min updates

Step 3: push 3 onto stack; min stays 1

Top -> [value: 3, min: 1] -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: 3 is bigger than current min 1, so min remains 1

Step 4: getMin returns 1

Top -> [value: 3, min: 1] -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: Top element stores current min, so return it directly

Step 5: pop top element (3)

Top -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: Remove top element, min updates to min stored in new top

Step 6: getMin returns 1

Top -> [value: 1, min: 1] -> [value: 5, min: 5] -> null

Why: Top element min is 1, so return it

Result:

Top -> [value: 1, min: 1] -> [value: 5, min: 5] -> null
getMin outputs: 1
getMin outputs: 1

Annotated Code

DSA Java

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val); // push new min
        } else {
            minStack.push(minStack.peek()); // repeat current min
        }
    }

    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(5);
        minStack.push(1);
        minStack.push(3);
        System.out.println(minStack.getMin()); // 1
        minStack.pop();
        System.out.println(minStack.getMin()); // 1
    }
}

if (minStack.isEmpty() || val <= minStack.peek()) {

check if new value is smaller or equal to current min to update minStack

minStack.push(val); // push new min

push new minimum value onto minStack

minStack.push(minStack.peek()); // repeat current min

repeat current minimum to keep stacks aligned

stack.pop(); minStack.pop();

pop both stacks to keep minStack synced with stack

return minStack.peek();

return current minimum in O(1) time

Output

1

1

Complexity Analysis

Time: O(1) for push, pop, and getMin because all operations use stack top access only

Space: O(n) because we store all elements and their minimums in two stacks

vs Alternative: Compared to scanning the stack for min each time (O(n)), this design gives O(1) min retrieval at the cost of extra space

Edge Cases

empty stack

pop and getMin do nothing or throw error if not checked

DSA Java

if (!stack.isEmpty()) {

push duplicate minimum values

minStack stores duplicates to keep correct min after pops

DSA Java

if (minStack.isEmpty() || val <= minStack.peek()) {

pop until empty

both stacks become empty safely

DSA Java

if (!stack.isEmpty()) {

When to Use This Pattern

When you need to get the minimum value from a stack quickly at any time, use the Min Stack pattern to track minimums alongside values.

Common Mistakes

Mistake: Only storing minimum values when they change, causing minStack and stack sizes to differ
Fix: Always push to minStack on every push to keep stacks aligned

Mistake: Not handling empty stack before pop or getMin causing errors
Fix: Check if stack is empty before popping or getting min

Summary

Keeps track of the minimum value in a stack at all times for quick retrieval.

Use when you need to get the smallest element in a stack in constant time.

Store the minimum value at each push to avoid scanning the stack later.

Practice

1. What is the main purpose of a Min Stack data structure?

easy

A. To retrieve the minimum element in constant time along with stack operations

B. To sort elements in ascending order automatically

C. To store only the minimum elements pushed so far

D. To reverse the order of elements pushed into the stack

Solution

1. Step 1: Understand stack operations

   A stack supports push, pop, and top operations in LIFO order.

2. Step 2: Identify Min Stack feature

   Min Stack extends stack by allowing retrieval of minimum element in O(1) time.

3. Final Answer:

   To retrieve the minimum element in constant time along with stack operations -> Option A

4. Quick Check:

   Min Stack = constant time min retrieval [OK]

Hint: Min Stack always tracks minimum for O(1) min retrieval [OK]

Common Mistakes:

• Thinking Min Stack sorts elements automatically
• Assuming Min Stack stores only minimum elements
• Confusing Min Stack with reversing stack order

2. Which of the following is the correct Java method signature to push an integer val onto a Min Stack?

easy

A. public int push(int val)

B. void push(int val) public

C. public void push(int val)

D. push public void(int val)

Solution

1. Step 1: Recall Java method syntax

   Java method signature starts with access modifier, return type, method name, and parameters.

2. Step 2: Check each option

   public void push(int val) follows correct syntax: public void push(int val). Others have wrong order or return type.

3. Final Answer:

   public void push(int val) -> Option C

4. Quick Check:

   Java method syntax = public void push(int val) [OK]

Hint: Java methods start with access modifier then return type [OK]

Common Mistakes:

• Placing 'public' after method name
• Using wrong return type for void methods
• Incorrect parameter placement

3. Given the following operations on a Min Stack:

MinStack minStack = new MinStack();
minStack.push(3);
minStack.push(5);
minStack.push(2);
minStack.push(1);
minStack.pop();
int min = minStack.getMin();
System.out.println(min);

What will be printed?

medium

A. 2

B. 1

C. 3

D. 5

Solution

1. Step 1: Trace push operations and min values

   Push 3 (min=3), push 5 (min=3), push 2 (min=2), push 1 (min=1).

2. Step 2: Pop removes top (1), min updates to previous min (2), then getMin returns 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   After pop, min = 2 [OK]

Hint: Pop updates min to previous minimum [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing top element with min
• Ignoring min update on pop

4. Consider this buggy Min Stack method snippet:

public void pop() {
  if(stack.isEmpty()) return;
  int top = stack.pop();
  if(top == minStack.peek()) {
    minStack.pop();
  }
}

What is the main issue here?

medium

A. It does not update minStack when pushing

B. It pops from stack twice accidentally

C. It compares top with minStack.pop() instead of peek()

D. It does not handle empty minStack before peek

Solution

1. Step 1: Analyze pop method safety

   Before calling minStack.peek(), we must ensure minStack is not empty to avoid error.

2. Step 2: Identify missing empty check on minStack

   Code checks stack but not minStack emptiness before peek, risking exception.

3. Final Answer:

   It does not handle empty minStack before peek -> Option D

4. Quick Check:

   Check minStack empty before peek [OK]

Hint: Always check stack emptiness before peek/pop [OK]

Common Mistakes:

• Ignoring minStack empty check
• Popping stack twice
• Confusing peek and pop methods

5. You want to design a Min Stack that supports push, pop, top, and getMin all in constant time. Which approach is best?

hard

A. Use one stack and scan all elements to find min on getMin

B. Use two stacks: one for all values, one for current minimums

C. Use a queue to store elements and find min by sorting

D. Use a linked list and traverse to find min on each getMin

Solution

1. Step 1: Understand time complexity requirements

   All operations must be O(1), so scanning or traversing is not allowed.

2. Step 2: Evaluate approaches

   Two stacks approach keeps track of minimums efficiently in O(1) time.

3. Final Answer:

   Use two stacks: one for all values, one for current minimums -> Option B

4. Quick Check:

   Two stacks = O(1) min retrieval [OK]

Hint: Two stacks track values and minimums separately [OK]

Common Mistakes:

• Using scanning which is O(n)
• Using queue which is not stack
• Traversing linked list on getMin