Min Stack Design in DSA C#

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 below it. When you add or remove plates, you update the note so you always know the smallest plate on top.

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

Dry Run Walkthrough

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

Goal: Maintain stack and quickly find the minimum value after each operation

Step 1: Push 5 onto stack

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

Why: First element, so min is 5

Step 2: Push 1 onto stack

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

Why: 1 is less than previous min 5, update min to 1

Step 3: Push 3 onto stack

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

Why: 3 is greater than current min 1, min stays 1

Step 4: GetMin returns 1

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

Why: Top node stores current min

Step 5: Pop top element (3)

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

Why: Remove top, min updates to next node's min

Step 6: GetMin returns 1

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

Why: Min is still 1 after pop

Result:

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class MinStack {
    private Stack<(int value, int min)> stack = new Stack<(int, int)>();

    public void Push(int val) {
        int currentMin = stack.Count == 0 ? val : Math.Min(val, stack.Peek().min);
        stack.Push((val, currentMin));
    }

    public void Pop() {
        if (stack.Count > 0) {
            stack.Pop();
        } else {
            throw new InvalidOperationException("Stack is empty");
        }
    }

    public int Top() {
        if (stack.Count > 0) {
            return stack.Peek().value;
        }
        throw new InvalidOperationException("Stack is empty");
    }

    public int GetMin() {
        if (stack.Count > 0) {
            return stack.Peek().min;
        }
        throw new InvalidOperationException("Stack is empty");
    }
}

public class Program {
    public static void Main() {
        MinStack minStack = new MinStack();
        minStack.Push(5);
        minStack.Push(1);
        minStack.Push(3);
        Console.WriteLine(minStack.GetMin()); // 1
        minStack.Pop();
        Console.WriteLine(minStack.GetMin()); // 1
    }
}

int currentMin = stack.Count == 0 ? val : Math.Min(val, stack.Peek().min);

Calculate new min by comparing pushed value with current min

stack.Push((val, currentMin));

Push value and current min as a pair onto stack

stack.Pop();

Remove top element, min updates automatically to next element's min

return stack.Peek().min;

Return current minimum from top element

Output

1

1

Complexity Analysis

Time: O(1) for push, pop, top, and getMin because all operations use stack peek or push/pop without loops

Space: O(n) because we store each element with its current min in the stack

vs Alternative: Compared to scanning the whole stack for min each time (O(n)), this design is much faster with O(1) min retrieval

Edge Cases

Empty stack when calling Pop or GetMin

Throws InvalidOperationException to signal invalid operation

DSA C#

if (stack.Count > 0) { ... } throw new InvalidOperationException("Stack is empty");

Push duplicate minimum values

Duplicates are stored with their min, so min remains correct after pops

DSA C#

int currentMin = stack.Count == 0 ? val : Math.Min(val, stack.Peek().min);

Single element stack

Min is that element itself, works normally

DSA C#

int currentMin = stack.Count == 0 ? val : Math.Min(val, stack.Peek().min);

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 values without tracking minimums, causing GetMin to be O(n)
Fix: Store each pushed value with the current minimum so GetMin is O(1)

Mistake: Updating min incorrectly when popping, losing track of correct minimum
Fix: Keep min with each element so popping restores previous min automatically

Summary

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

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

Store the current minimum with each element to maintain O(1) min retrieval.

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 the Min Stack concept

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

2. Step 2: Identify the main 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:

• Confusing Min Stack with sorting
• Thinking it behaves like a queue
• Assuming it reverses elements

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

easy

A. public void Push(string val)

B. public int Push(int val)

C. void Push()

D. public void Push(int val)

Solution

1. Step 1: Check method return type and parameters

   Push method should not return a value, so return type is void, and it takes an int parameter.

2. Step 2: Match the correct signature

   public void Push(int val) matches: public void Push(int val)

3. Final Answer:

   public void Push(int val) -> Option D

4. Quick Check:

   Push method = void + int parameter [OK]

Hint: Push returns void and takes int parameter [OK]

Common Mistakes:

• Using wrong return type like int
• Missing parameter in method
• Using wrong parameter type like string

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();
Console.WriteLine(min);

What will be printed?

medium

A. 1

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace the stack after each operation

   Push 3 -> stack: [3], min=3 Push 5 -> stack: [3,5], min=3 Push 2 -> stack: [3,5,2], min=2 Push 1 -> stack: [3,5,2,1], min=1 Pop -> removes 1, stack: [3,5,2], min=2

2. Step 2: GetMin after pop

   Minimum is now 2 after popping 1.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Min after pop = 2 [OK]

Hint: Pop removes min, next min updates correctly [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing stack top with min
• Ignoring pop effect on min

4. Consider this buggy Min Stack pop method:

public void Pop() {
    if(stack.Count > 0) {
        stack.Pop();
        minStack.Pop();
    }}

What is the main issue with this implementation?

medium

A. It does not check if stack is empty before popping

B. It pushes elements instead of popping

C. It pops from minStack even when the popped element is not the minimum

D. It returns a value but method is void

Solution

1. Step 1: Understand the role of minStack

   minStack should only pop when the popped element equals the current minimum.

2. Step 2: Identify the bug

   This code pops minStack every time, even if the popped element is not minimum, causing incorrect min tracking.

3. Final Answer:

   It pops from minStack even when the popped element is not the minimum -> Option C

4. Quick Check:

   Pop minStack only if popped element == min [OK]

Hint: Pop minStack only if popped element equals current min [OK]

Common Mistakes:

• Always popping minStack blindly
• Not checking stack emptiness (not in this code)
• Confusing push and pop operations

5. You want to design a Min Stack that supports Push, Pop, Top, and GetMin all in O(1) time. Which approach is best?

hard

A. Use two stacks: one for all elements, one for current minimums

B. Use a single stack and sort it after each push

C. Use a queue to track minimum elements

D. Store all elements in a list and scan for min on GetMin

Solution

1. Step 1: Analyze time complexity requirements

   All operations must be O(1), so sorting or scanning is too slow.

2. Step 2: Identify suitable data structure

   Using two stacks, one for elements and one for minimums, allows constant time min retrieval.

3. Final Answer:

   Use two stacks: one for all elements, one for current minimums -> Option A

4. Quick Check:

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

Hint: Two stacks track elements and minimums efficiently [OK]

Common Mistakes:

• Sorting stack after each push (slow)
• Using queue instead of stack
• Scanning list for min on each GetMin