Min Stack Design in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Min Stack?

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

intermediate

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

It keeps an extra stack that stores the minimum values at each level, so the current minimum is always on top of this extra stack.

beginner

What operations must a Min Stack support?

Push (add element), Pop (remove element), Top (get top element), and GetMin (get minimum element) all in constant time.

beginner

Why can't we just scan the stack to find the minimum each time?

Scanning the stack each time would take linear time, which is slow. Min Stack design keeps minimum retrieval in constant time.

intermediate

What happens to the minimum stack when we pop the main stack?

We also pop the minimum stack if the popped element is the current minimum, keeping both stacks in sync.

What extra data structure is commonly used in Min Stack design to track minimum values?

A Linked list

B Queue

C Hash map

D Another stack

A second stack is used to keep track of minimum values at each push.

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

A O(n)

B O(log n)

C O(1)

D O(n^2)

Min Stack retrieves the minimum element in constant time O(1).

When pushing a new element, when do we push it onto the minimum stack?

A Never

B Only if it is smaller or equal to the current minimum

C Always

D Only if it is larger than the current minimum

We push onto the minimum stack only if the new element is smaller or equal to the current minimum.

What happens to the minimum stack when the top element is popped from the main stack and it equals the current minimum?

A Pop from the minimum stack as well

B Do nothing

C Push a new minimum

D Clear the minimum stack

We pop from the minimum stack to keep it in sync with the main stack.

Which of these is NOT a required operation for a Min Stack?

A Sort

B Pop

C GetMin

D Push

Sorting is not required; Min Stack only needs push, pop, top, and getMin.

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

Think about syncing two stacks to track minimum.

Describe the time complexity of each operation in a Min Stack and why it is efficient.

Focus on how the extra stack helps avoid slow searches.