Min Stack Design in DSA C# - Build from Scratch

Min Stack Design

📖 Scenario: Imagine you are building a special stack for a calculator app. This stack not only stores numbers but also quickly tells you the smallest number currently in the stack. This helps the calculator show the minimum value instantly without searching through all numbers.

🎯 Goal: Create a MinStack class that supports these operations: Push to add a number, Pop to remove the top number, Top to see the top number, and GetMin to get the smallest number in the stack at any time.

📋 What You'll Learn

Create a MinStack class with a constructor

Implement Push(int val) to add a number

Implement Pop() to remove the top number

Implement Top() to return the top number

Implement GetMin() to return the smallest number

Use two stacks internally: one for all numbers, one for tracking minimums

💡 Why This Matters

🌍 Real World

Min Stacks are useful in applications like calculators, stock price tracking, or any system needing quick access to minimum values during data processing.

💼 Career

Understanding Min Stack design helps in coding interviews and real-world software development where efficient data retrieval is critical.

1

Create the MinStack class with two stacks

Create a public class called MinStack with a constructor that initializes two private stacks: stack and minStack, both of type Stack<int>.

DSA C#

public class MinStack
{
    private Stack stack;
    private Stack minStack;

    public MinStack()
    {
        // Your code here
    }
}

Hint

Use stack = new Stack(); and minStack = new Stack(); inside the constructor.

2

Implement the Push method

Add a public method Push that takes an int val. It should push val onto stack. Then, push val onto minStack if minStack is empty or val is less than or equal to the current top of minStack. Otherwise, push the current top of minStack again to keep track of the minimum.

DSA C#

using System.Collections.Generic;

public class MinStack
{
    private Stack stack;
    private Stack minStack;

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

    public void Push(int val)
    {
        // Your code here
    }
}

Hint

Push val to stack. For minStack, push val if it's smaller or equal to current min, else push the current min again.

3

Implement Pop and Top methods

Add two public methods: Pop() that removes the top element from both stack and minStack, and Top() that returns the top element of stack without removing it.

DSA C#

using System.Collections.Generic;

public class MinStack
{
    private Stack stack;
    private Stack minStack;

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

    public void Push(int val)
    {
        stack.Push(val);
        if (minStack.Count == 0 || val <= minStack.Peek())
        {
            minStack.Push(val);
        }
        else
        {
            minStack.Push(minStack.Peek());
        }
    }

    public void Pop()
    {
        // Your code here
    }

    public int Top()
    {
        // Your code here
    }
}

Hint

Pop from both stacks in Pop(). Return stack.Peek() in Top().

4

Implement GetMin method and print test output

Add a public method GetMin() that returns the top element of minStack. Then, create a Main method to test your MinStack by pushing 3, 5, 2, 1, popping once, and printing the results of Top() and GetMin().

DSA C#

using System;
using System.Collections.Generic;

public class MinStack
{
    private Stack stack;
    private Stack minStack;

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

    public void Push(int val)
    {
        stack.Push(val);
        if (minStack.Count == 0 || val <= minStack.Peek())
        {
            minStack.Push(val);
        }
        else
        {
            minStack.Push(minStack.Peek());
        }
    }

    public void Pop()
    {
        stack.Pop();
        minStack.Pop();
    }

    public int Top()
    {
        return stack.Peek();
    }

    public int GetMin()
    {
        // Your code here
    }

    public static void Main()
    {
        // Your code here
    }
}

Hint

Return minStack.Peek() in GetMin(). In Main(), push 3, 5, 2, 1, pop once, then print Top() and GetMin().

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