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 keep track of the minimum values at each level, 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 retrieving the minimum element from a Min Stack?

The time complexity is O(1) because the minimum element is always on top of the auxiliary min stack.

intermediate

Why do we need to pop from both the main stack and the min stack in a Min Stack?

Because when the top element is removed from the main stack, if it is the current minimum, it must also be removed from the min stack to update the minimum correctly.

What data structure is commonly used alongside the main stack in a Min Stack design?

A Hash map for element counts

B Queue to track elements

C Linked list to store minimums

D Another stack to track minimum values

An auxiliary stack is used to keep track of minimum values at each push.

What is the time complexity of the push operation in a Min Stack?

A O(n)

B O(log n)

C O(1)

D O(n^2)

Push operation is O(1) because it involves pushing onto the main stack and possibly the min stack.

When popping from a Min Stack, when do you pop from the min stack?

A Only if popped element equals current minimum

B Always pop from min stack

C Never pop from min stack

D Pop from min stack if stack size is even

Pop from min stack only if the popped element is the current minimum.

What does the top of the min stack represent at any time?

A The maximum element in the stack

B The minimum element in the stack

C The last pushed element

D The size of the stack

The top of the min stack always holds the current minimum element.

Which operation is NOT supported efficiently by a Min Stack?

A Get median

B Pop

C Push

D Get minimum

Min Stack does not support efficient median retrieval.

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

Think about how two stacks work together to track minimum.

Describe the time complexity of push, pop, and getMin operations in a Min Stack and why.

Focus on how auxiliary stack helps avoid scanning.