Min Stack Design in DSA Go

Mental Model

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

Analogy: Imagine a stack of plates where each plate also shows the smallest plate size below it, so you always know the smallest plate on top.

Stack top
  ↓
[7, min=3] -> [3, min=3] -> [5, min=5] -> null

Dry Run Walkthrough

Input: Push 5, Push 3, Push 7, GetMin, Pop, GetMin

Goal: Show how the stack keeps track of minimum values after each operation

Step 1: Push 5 onto stack

[5, min=5] -> null

Why: First element is the minimum so min is 5

Step 2: Push 3 onto stack

[3, min=3] -> [5, min=5] -> null

Why: 3 is less than previous min 5, so min updates to 3

Step 3: Push 7 onto stack

[7, min=3] -> [3, min=3] -> [5, min=5] -> null

Why: 7 is greater than current min 3, so min stays 3

Step 4: GetMin returns 3

[7, min=3] -> [3, min=3] -> [5, min=5] -> null

Why: Minimum is stored at top node, so return 3

Step 5: Pop top element (7)

[3, min=3] -> [5, min=5] -> null

Why: Remove top, min remains 3 from next node

Step 6: GetMin returns 3

[3, min=3] -> [5, min=5] -> null

Why: Minimum is still 3 after pop

Result:

[3, min=3] -> [5, min=5] -> null
Minimum after last operation: 3

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Node struct {
	value int
	min   int
	next  *Node
}

type MinStack struct {
	top *Node
}

func Constructor() MinStack {
	return MinStack{top: nil}
}

func (s *MinStack) Push(val int) {
	if s.top == nil {
		s.top = &Node{value: val, min: val, next: nil}
		return
	}
	currentMin := s.top.min
	newMin := val
	if val > currentMin {
		newMin = currentMin
	}
	newNode := &Node{value: val, min: newMin, next: s.top}
	s.top = newNode
}

func (s *MinStack) Pop() {
	if s.top != nil {
		s.top = s.top.next
	}
}

func (s *MinStack) Top() int {
	if s.top != nil {
		return s.top.value
	}
	return -1 // or error value
}

func (s *MinStack) GetMin() int {
	if s.top != nil {
		return s.top.min
	}
	return -1 // or error value
}

func main() {
	stack := Constructor()
	stack.Push(5)
	stack.Push(3)
	stack.Push(7)
	fmt.Println(stack.GetMin()) // expect 3
	stack.Pop()
	fmt.Println(stack.GetMin()) // expect 3
}

if s.top == nil { s.top = &Node{value: val, min: val, next: nil} return }

initialize stack with first node where min equals value

currentMin := s.top.min newMin := val if val > currentMin { newMin = currentMin }

calculate new min by comparing pushed value with current min

newNode := &Node{value: val, min: newMin, next: s.top} s.top = newNode

push new node on top with updated min

if s.top != nil { s.top = s.top.next }

pop top node by moving top pointer to next

if s.top != nil { return s.top.min }

return min stored at top node

Output

3

3

Complexity Analysis

Time: O(1) for push, pop, and getMin because we only update or read the top node

Space: O(n) because we store min value with each node for all n elements

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

Edge Cases

Empty stack when calling Pop or GetMin

Pop does nothing, GetMin returns -1 indicating no elements

DSA Go

if s.top != nil {

Push duplicate minimum values

Min remains correct because each node stores min up to that point

DSA Go

currentMin := s.top.min

Pop until stack is empty

Stack top becomes nil safely, no errors on further Pop or GetMin

DSA Go

if s.top != nil { s.top = s.top.next }

When to Use This Pattern

When you need to get the minimum value from a stack quickly at any time, use Min Stack pattern to store minimums with each element.

Common Mistakes

Mistake: Only storing values in stack without tracking minimums, causing O(n) min retrieval
Fix: Store the minimum value along with each pushed element to get O(1) min

Mistake: Updating min incorrectly by not comparing new value with current min
Fix: Always compare new value with current min and store the smaller one

Summary

Keeps track of minimum value at every stack level for quick retrieval.

Use when you want to get minimum element in constant time while pushing and popping.

Store the minimum so far with each element to avoid scanning the whole stack.

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