Min Stack Design in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Min Stack after Push and Pop

What is the output of the min stack after performing the following operations?

Operations:
push(5), push(3), push(7), pop(), getMin(), pop(), getMin()

DSA C#

MinStack stack = new MinStack();
stack.Push(5);
stack.Push(3);
stack.Push(7);
stack.Pop();
int min1 = stack.GetMin();
stack.Pop();
int min2 = stack.GetMin();
Console.WriteLine($"{min1} {min2}");

A 3 5

B 5 3

C 7 5

D 3 7

💡 Hint

Remember the min stack keeps track of the smallest element at each push.

After pushing 5, 3, 7, the stack is [5,3,7]. Popping removes 7. getMin() returns 3. Popping removes 3. getMin() returns 5.

❓ Predict Output

intermediate

Value of Min after Sequence of Operations

After executing these operations on a min stack:
push(2), push(2), push(1), pop(), getMin(), pop(), getMin()
What is the output of the two getMin() calls?

DSA C#

MinStack stack = new MinStack();
stack.Push(2);
stack.Push(2);
stack.Push(1);
stack.Pop();
int min1 = stack.GetMin();
stack.Pop();
int min2 = stack.GetMin();
Console.WriteLine($"{min1} {min2}");

A 1 1

B 1 2

C 2 2

D 2 1

💡 Hint

Check how duplicates of the minimum value are handled.

After pushing 2,2,1, stack is [2,2,1]. Pop removes 1. getMin() is 2. Pop removes 2. getMin() remains 2.

🔧 Debug

advanced

Identify the Bug in Min Stack Push Method

Given this push method for a min stack, what is the bug causing incorrect min values?

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

DSA C#

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

A Pushes x twice causing stack overflow

B Does not push x when stack is empty

C Uses wrong comparison operator, should be x > minStack.Peek()

D Does not push x when x equals current min, causing wrong min after pop

💡 Hint

Think about what happens when the new value equals the current minimum.

The condition x < minStack.Peek() excludes equal values, so duplicates of min are not pushed. When popping min, minStack loses track of duplicates causing wrong min.

🚀 Application

advanced

Minimum Element Tracking in Real-Time Data Stream

You want to design a system that tracks the minimum value in a stream of integers arriving in real-time. Which data structure approach best suits this requirement?

A Use a Min Stack that pushes each new element and pops when elements expire

B Use a simple stack and scan all elements to find min after each insertion

C Use a queue and sort it after each insertion to find min

D Use a hash set to store elements and find min by iterating

💡 Hint

Think about efficient min retrieval after each update.

Min Stack allows O(1) min retrieval by tracking minimums during push/pop, suitable for real-time streams with element expiration.

🧠 Conceptual

expert

Space Complexity of Min Stack Design

What is the worst-case space complexity of a Min Stack that stores all elements and tracks minimums using an auxiliary stack?

A O(n^2), quadratic space due to duplicate tracking

B O(n), where n is the number of elements pushed

C O(log n), logarithmic space due to min tracking

D O(1), constant space regardless of elements

💡 Hint

Consider how many elements the auxiliary min stack can hold in the worst case.

In worst case, each pushed element is smaller or equal to previous min, so auxiliary stack stores all elements, leading to O(n) space.

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