Min Stack Design in DSA Go - Execution Trace

Concept Flow - Min Stack Design

Push value

↓

Compare with current min

↓

If smaller or equal, push to min stack

↓

Push to main stack

↓

Pop value

↓

Check if popped value == min stack top

↓

If yes, pop min stack

↓

GetMin

↓

Return top of min stack

This flow shows how values are pushed and popped from the main stack and min stack to keep track of the minimum value efficiently.

Execution Sample

DSA Go

push(5)
push(3)
push(7)
pop()
getMin()

This code pushes 5, 3, 7 onto the stack, pops the top (7), then gets the current minimum value.

Execution Table

Step	Operation	Main Stack	Min Stack	Pointer Changes	Visual State
1	push(5)	[5]	[5]	Push 5 to main and min stacks	Main: 5 -> null; Min: 5 -> null
2	push(3)	[5, 3]	[5, 3]	3 <= min(5), push 3 to min stack	Main: 5 -> 3 -> null; Min: 5 -> 3 -> null
3	push(7)	[5, 3, 7]	[5, 3]	7 > min(3), push only to main stack	Main: 5 -> 3 -> 7 -> null; Min: 5 -> 3 -> null
4	pop()	[5, 3]	[5, 3]	Pop 7 from main stack; 7 != min(3), min stack unchanged	Main: 5 -> 3 -> null; Min: 5 -> 3 -> null
5	getMin()	[5, 3]	[5, 3]	Return top of min stack: 3	Min value: 3
6	pop()	[5]	[5]	Pop 3 from main stack; 3 == min(3), pop min stack	Main: 5 -> null; Min: 5 -> null
7	getMin()	[5]	[5]	Return top of min stack: 5	Min value: 5
8	pop()	[]	[]	Pop 5 from main stack; 5 == min(5), pop min stack	Main: empty; Min: empty
9	getMin()	[]	[]	Stack empty, no min value	Min value: None

💡 Execution stops after all operations are performed.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
Main Stack	[]	[5]	[5,3]	[5,3,7]	[5,3]	[5,3]	[5]	[5]	[]	[]
Min Stack	[]	[5]	[5,3]	[5,3]	[5,3]	[5,3]	[5]	[5]	[]	[]
Min Value	None	5	3	3	3	3	5	5	None	None

Key Moments - 3 Insights

Why do we push the value onto the min stack only if it is smaller or equal to the current min?

Because the min stack keeps track of minimum values. If a new value is smaller or equal, it could be the new minimum. This is shown in execution_table rows 1, 2, and 3 where min stack updates only when the pushed value is <= current min.

What happens to the min stack when we pop a value that is not the current minimum?

The min stack remains unchanged because the popped value is not the minimum. This is shown in execution_table row 4 where popping 7 does not change the min stack.

How do we get the minimum value efficiently at any time?

We return the top value of the min stack, which always holds the current minimum. This is shown in execution_table rows 5 and 7 where getMin returns the top of min stack.

Visual Quiz - 3 Questions

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

A [5, 3, 7]

B [5, 3]

C [7]

D [3]

💡 Hint

Check the 'Min Stack' column at step 3 in the execution_table.

At which step does the min stack pop a value because the popped main stack value equals the min?

A Step 6

B Step 8

C Step 4

D Step 9

💡 Hint

Look for steps where 'Pointer Changes' mention popping min stack due to equality.

If we push a value smaller than current min, what happens to the min stack?

A The min stack is cleared

B It remains unchanged

C The value is pushed onto min stack

D The value replaces the bottom of min stack

💡 Hint

Refer to the concept_flow and execution_table steps 1 and 2.

Concept Snapshot

Min Stack Design:
- Use two stacks: main stack and min stack
- Push: add to main stack; if value <= min stack top, push to min stack
- Pop: remove from main stack; if popped == min stack top, pop min stack
- getMin: return top of min stack
- Keeps track of minimum in O(1) time

Full Transcript

Min Stack Design uses two stacks to track values and minimums. When pushing, the value goes to the main stack. If it is smaller or equal to the current minimum, it also goes to the min stack. When popping, if the popped value equals the min stack's top, pop min stack too. Getting the minimum returns the top of the min stack. This keeps minimum retrieval in constant time.

Practice

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

easy

A. To retrieve the minimum element in constant time

B. To sort elements in ascending order

C. To store elements in a queue fashion

D. To reverse the order of elements

Solution

1. Step 1: Understand Min Stack functionality

   A Min Stack is designed to keep track of the minimum element efficiently.

2. Step 2: Identify the key feature

   It allows retrieving the minimum element in constant time, unlike a normal stack.

3. Final Answer:

   To retrieve the minimum element in constant time -> Option A

4. Quick Check:

   Min Stack = Fast minimum retrieval [OK]

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

Common Mistakes:

• Thinking it sorts elements
• Confusing with queue behavior
• Assuming it reverses elements

2. Which of the following Go code snippets correctly declares a Min Stack struct with two slices for values and minimums?

easy

A. type MinStack struct { values map[int]int; mins []int }

B. type MinStack struct { values []int; min int }

C. type MinStack struct { values []int; mins []int }

D. type MinStack struct { values []int; mins int }

Solution

1. Step 1: Check struct fields for Min Stack

   Min Stack needs slices to store all values and track minimums at each push.

2. Step 2: Validate field types

   Both values and mins should be slices of int for stack behavior.

3. Final Answer:

   type MinStack struct { values []int; mins []int } -> Option C

4. Quick Check:

   Two int slices = correct Min Stack struct [OK]

Hint: Min Stack uses two int slices for values and mins [OK]

Common Mistakes:

• Using map instead of slice for values
• Using int instead of slice for mins
• Mixing types between fields

3. Given the following Go code for a Min Stack, what will be printed after the operations?

ms := MinStack{}
ms.Push(3)
ms.Push(5)
ms.Push(2)
ms.Push(1)
ms.Pop()
fmt.Println(ms.GetMin())

medium

A. 2

B. 1

C. 3

D. 5

Solution

1. Step 1: Trace Push operations and minimums

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

2. Step 2: Pop removes last pushed (1), so min updates to previous min (2)

   After pop, minimum is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Pop last min 1, new min = 2 [OK]

Hint: Pop removes last min, so min updates to previous min [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing push order
• Not updating min stack on pop

4. Identify the bug in this Go Min Stack Pop method:

func (ms *MinStack) Pop() {
  ms.values = ms.values[:len(ms.values)-1]
  ms.mins = ms.mins[:len(ms.mins)]
}

medium

A. Pop method should return the popped value

B. The values slice is not shortened on pop

C. Pop method should clear both slices completely

D. The mins slice is not shortened on pop

Solution

1. Step 1: Analyze slice operations in Pop

   Values slice is shortened by one element correctly.

2. Step 2: Check mins slice operation

   Mins slice is sliced to full length, so it is not shortened, causing mismatch.

3. Final Answer:

   The mins slice is not shortened on pop -> Option D

4. Quick Check:

   mins slice must shrink with values [OK]

Hint: Pop must shrink both values and mins slices equally [OK]

Common Mistakes:

• Forgetting to shrink mins slice
• Assuming Pop returns value
• Clearing slices fully on pop

5. You want to design a Min Stack that supports Push, Pop, Top, and GetMin all in O(1) time. Which approach below correctly handles the minimum tracking when pushing a new element x?

hard

A. Push x to values; push x only if x < current min to mins

B. Push x to values; push min(x, current min) to mins

C. Push x to values; push current min only if x > current min to mins

D. Push x to values; do not update mins slice

Solution

1. Step 1: Understand min tracking logic

   Each push must record the minimum so far to allow O(1) GetMin.

2. Step 2: Compare new element with current min

   Push the smaller of x and current min onto mins slice to keep track.

3. Final Answer:

   Push x to values; push min(x, current min) to mins -> Option B

4. Quick Check:

   Always push min(x, current min) to mins [OK]

Hint: Always push min of new and current min to mins stack [OK]

Common Mistakes:

• Pushing x only if smaller causes missing mins
• Not updating mins on every push
• Ignoring mins slice updates