Min Stack Design in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of a Min Stack?

A Min Stack is a special stack that supports retrieving the minimum element in constant time, along with normal stack operations like push and pop.

intermediate

How does a Min Stack keep track of the minimum element efficiently?

It uses an auxiliary stack to store the minimum values at each state, so the current minimum can be retrieved in O(1) time.

beginner

In Min Stack design, what happens when you push a new element smaller than or equal to the current minimum?

You push the new element onto the main stack and also push it onto the min stack because it becomes the new minimum.

beginner

What is the time complexity of push, pop, and getMin operations in a Min Stack?

All operations (push, pop, getMin) run in constant time O(1).

intermediate

Why do we need two stacks in Min Stack design instead of one?

One stack stores all elements, and the other keeps track of minimum elements at each point, allowing quick access to the minimum without scanning all elements.

What does the auxiliary stack in a Min Stack store?

A Only the maximum elements

B All elements in sorted order

C Random elements

D Minimum elements at each state

The auxiliary stack stores the minimum elements corresponding to each state of the main stack.

What is the time complexity to get the minimum element from a Min Stack?

A O(log n)

B O(1)

C O(n)

D O(n^2)

The Min Stack is designed to retrieve the minimum element in constant time O(1).

When popping from a Min Stack, what must you do with the min stack?

A Always pop from min stack

B Never pop from min stack

C Pop from min stack only if top equals popped element

D Push a new element to min stack

You pop from the min stack only if the top of the min stack equals the popped element from the main stack to keep both stacks synchronized.

If the new element pushed is greater than the current minimum, what happens to the min stack?

A Push the current minimum again to min stack

B Push the new element to min stack

C Do not push anything to min stack

D Clear the min stack

The current minimum is pushed again to keep the min stack aligned with the main stack size.

Which data structure is best suited to implement a Min Stack?

A Stack

B Linked List

C Heap

D Queue

A stack is the best data structure to implement Min Stack because it supports push and pop operations efficiently.

Explain how a Min Stack maintains the minimum element during push and pop operations.

Think about how the min stack mirrors the main stack to track minimums.

Describe the advantages of using a Min Stack over a normal stack when minimum retrieval is needed.

Consider time complexity and operation efficiency.

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