Min Stack Design in DSA Java - 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 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 at the 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 typically used alongside the main stack in a Min Stack design?

A Queue to track order

B Auxiliary stack to track minimums

C Hash map to store counts

D Linked list for fast access

An auxiliary stack is used to keep track of the minimum elements at each state.

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

A O(1) for all

B O(n) for getMin

C O(log n) for push

D O(n) for pop

All operations including getMin run in constant time O(1) in a Min Stack.

When pushing a new element equal to the current minimum, what should happen in the min stack?

A Clear the min stack

B Do not push onto the min stack

C Pop the min stack

D Push the new element onto the min stack

Equal minimum values are pushed onto the min stack to keep track of duplicates.

If the main stack is empty, what should getMin() return or do?

A Return the last minimum

B Return zero

C Return an error or indicate empty stack

D Return the maximum element

If the stack is empty, getMin should handle this gracefully, usually by error or special value.

Why is it not enough to keep only one minimum value variable in Min Stack design?

A Because minimum can change after popping elements

B Because variables are slow

C Because stacks cannot store variables

D Because minimum is always the first element

The minimum can change when elements are popped, so we need to track minimums at each state.

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

Think about how the min stack mirrors the main stack for minimum values.

Describe the time complexity of all operations in a Min Stack and why it is efficient.

Focus on how the auxiliary stack helps avoid scanning.

Practice

1. What is the main purpose of a Min Stack data structure?

easy

A. To retrieve the minimum element in constant time along with stack operations

B. To sort elements in ascending order automatically

C. To store only the minimum elements pushed so far

D. To reverse the order of elements pushed into the stack

Solution

1. Step 1: Understand stack operations

   A stack supports push, pop, and top operations in LIFO order.

2. Step 2: Identify Min Stack feature

   Min Stack extends stack by allowing retrieval of minimum element in O(1) time.

3. Final Answer:

   To retrieve the minimum element in constant time along with stack operations -> Option A

4. Quick Check:

   Min Stack = constant time min retrieval [OK]

Hint: Min Stack always tracks minimum for O(1) min retrieval [OK]

Common Mistakes:

• Thinking Min Stack sorts elements automatically
• Assuming Min Stack stores only minimum elements
• Confusing Min Stack with reversing stack order

2. Which of the following is the correct Java method signature to push an integer val onto a Min Stack?

easy

A. public int push(int val)

B. void push(int val) public

C. public void push(int val)

D. push public void(int val)

Solution

1. Step 1: Recall Java method syntax

   Java method signature starts with access modifier, return type, method name, and parameters.

2. Step 2: Check each option

   public void push(int val) follows correct syntax: public void push(int val). Others have wrong order or return type.

3. Final Answer:

   public void push(int val) -> Option C

4. Quick Check:

   Java method syntax = public void push(int val) [OK]

Hint: Java methods start with access modifier then return type [OK]

Common Mistakes:

• Placing 'public' after method name
• Using wrong return type for void methods
• Incorrect parameter placement

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();
System.out.println(min);

What will be printed?

medium

A. 2

B. 1

C. 3

D. 5

Solution

1. Step 1: Trace push operations and min values

   Push 3 (min=3), push 5 (min=3), push 2 (min=2), push 1 (min=1).

2. Step 2: Pop removes top (1), min updates to previous min (2), then getMin returns 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   After pop, min = 2 [OK]

Hint: Pop updates min to previous minimum [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing top element with min
• Ignoring min update on pop

4. Consider this buggy Min Stack method snippet:

public void pop() {
  if(stack.isEmpty()) return;
  int top = stack.pop();
  if(top == minStack.peek()) {
    minStack.pop();
  }
}

What is the main issue here?

medium

A. It does not update minStack when pushing

B. It pops from stack twice accidentally

C. It compares top with minStack.pop() instead of peek()

D. It does not handle empty minStack before peek

Solution

1. Step 1: Analyze pop method safety

   Before calling minStack.peek(), we must ensure minStack is not empty to avoid error.

2. Step 2: Identify missing empty check on minStack

   Code checks stack but not minStack emptiness before peek, risking exception.

3. Final Answer:

   It does not handle empty minStack before peek -> Option D

4. Quick Check:

   Check minStack empty before peek [OK]

Hint: Always check stack emptiness before peek/pop [OK]

Common Mistakes:

• Ignoring minStack empty check
• Popping stack twice
• Confusing peek and pop methods

5. You want to design a Min Stack that supports push, pop, top, and getMin all in constant time. Which approach is best?

hard

A. Use one stack and scan all elements to find min on getMin

B. Use two stacks: one for all values, one for current minimums

C. Use a queue to store elements and find min by sorting

D. Use a linked list and traverse to find min on each getMin

Solution

1. Step 1: Understand time complexity requirements

   All operations must be O(1), so scanning or traversing is not allowed.

2. Step 2: Evaluate approaches

   Two stacks approach keeps track of minimums efficiently in O(1) time.

3. Final Answer:

   Use two stacks: one for all values, one for current minimums -> Option B

4. Quick Check:

   Two stacks = O(1) min retrieval [OK]

Hint: Two stacks track values and minimums separately [OK]

Common Mistakes:

• Using scanning which is O(n)
• Using queue which is not stack
• Traversing linked list on getMin