Min Stack Design in DSA Java - Execution Trace

Concept Flow - Min Stack Design

Push x

↓

Push x to main stack

↓

Compare x with current min

Yes No↓

Push x to min stack

↓

Done

↓

Done

↓

Pop

↓

Pop from main stack

↓

Pop from min stack

↓

Done

↓

GetMin

↓

Return top of min stack

↓

Done

When pushing, add element to main stack and update min stack with new min. When popping, remove from both stacks. GetMin returns top of min stack.

Execution Sample

DSA Java

MinStack stack = new MinStack();
stack.push(3);
stack.push(5);
stack.push(2);
stack.pop();
int min = stack.getMin();

Push 3, 5, 2; pop top; get current minimum.

Execution Table

Step	Operation	Main Stack	Min Stack	Pointer Changes	Visual State
1	push(3)	[3]	[3]	Push 3 to main and min stacks	Main: 3 -> null; Min: 3 -> null
2	push(5)	[3,5]	[3,3]	Push 5 to main; min stack top is 3, 5 > 3, push 3 again	Main: 3 -> 5 -> null; Min: 3 -> 3 -> null
3	push(2)	[3,5,2]	[3,3,2]	Push 2 to main; 2 < min top 3, push 2 to min	Main: 3 -> 5 -> 2 -> null; Min: 3 -> 3 -> 2 -> null
4	pop()	[3,5]	[3,3]	Pop top 2 from main and min stacks	Main: 3 -> 5 -> null; Min: 3 -> 3 -> null
5	getMin()	[3,5]	[3,3]	Return top of min stack: 3	Main: 3 -> 5 -> null; Min: 3 -> 3 -> null

💡 After pop, min stack top is 3, so getMin returns 3.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
Main Stack	[]	[3]	[3,5]	[3,5,2]	[3,5]	[3,5]
Min Stack	[]	[3]	[3,3]	[3,3,2]	[3,3]	[3,3]
Current Min	N/A	3	3	2	3	3

Key Moments - 3 Insights

Why do we push the current min again to the min stack when the new element is not smaller?

Because the min stack must always have the min value corresponding to each element in the main stack. See step 2 in execution_table where 3 is pushed again to keep min aligned.

What happens if we pop from an empty stack?

The code should handle empty stack cases to avoid errors. In this example, popping is only done when stacks are non-empty as shown in step 4.

Why do we pop from both main and min stacks together?

Because each element in main stack has a corresponding min value in min stack. Popping both keeps them synchronized, as shown in step 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the top of the min stack?

A 2

B 3

C 5

D None

💡 Hint

Check the Min Stack column at step 3 in execution_table.

At which step does the min stack push the current min again instead of the new element?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at Pointer Changes column in execution_table for step 2.

If we pop at step 4, what will be the new top of the min stack?

A 2

B 3

C 5

D Empty

💡 Hint

See Min Stack column after step 4 in execution_table.

Concept Snapshot

Min Stack uses two stacks: main stack for all elements, min stack for current minimums.
Push: add to main; push min(new element, current min) to min stack.
Pop: remove from both stacks.
GetMin: return top of min stack.
Keeps min retrieval in O(1) time.

Full Transcript

Min Stack Design uses two stacks to track elements and minimums. When pushing, the element goes to the main stack. The min stack gets the smaller between the new element and current min. When popping, both stacks pop to stay aligned. Getting the minimum is just reading the top of the min stack. This keeps minimum retrieval fast and simple. The execution table shows pushing 3, 5, 2, popping once, and then getting the minimum which is 3. The variable tracker shows how stacks grow and shrink together. Key moments clarify why min stack duplicates values and why popping both stacks is necessary.

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