Min Stack Design in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Min Stack after push and pop operations

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

Operations:
push(3), push(5), push(2), push(1), pop(), getMin(), pop(), getMin()

DSA Java

class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        stack.pop();
    }

    public int getMin() {
        return minStack.peek();
    }
}

MinStack ms = new MinStack();
ms.push(3);
ms.push(5);
ms.push(2);
ms.push(1);
ms.pop();
int firstMin = ms.getMin();
ms.pop();
int secondMin = ms.getMin();
System.out.println(firstMin + "," + secondMin);

A 3,5

B 1,2

C 2,3

D 5,3

💡 Hint

Remember that getMin returns the smallest element currently in the stack.

After pushing 3,5,2,1, the stack is [3,5,2,1]. Popping once removes 1. getMin now returns 2. Popping again removes 2. getMin now returns 3.

🧠 Conceptual

intermediate

Understanding Min Stack Space Complexity

What is the worst-case space complexity of a Min Stack that stores the minimum values alongside the main stack?

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

B O(log n), logarithmic space usage

C O(1), constant space regardless of elements

D O(n^2), quadratic space usage

💡 Hint

Consider when every pushed element is smaller than the previous minimum.

In the worst case, every new element is smaller or equal to the current minimum, so the min stack stores all elements, leading to O(n) space.

🔧 Debug

advanced

Identify the bug in Min Stack pop method

What error will occur when running this pop method in Min Stack if the stack is empty?

DSA Java

public void pop() {
    if (stack.peek().equals(minStack.peek())) {
        minStack.pop();
    }
    stack.pop();
}

A NullPointerException when comparing elements

B EmptyStackException when calling peek() on empty stack

C No error, method works fine

D IndexOutOfBoundsException when popping

💡 Hint

What happens if pop is called on an empty stack?

Calling peek() on an empty stack throws EmptyStackException in Java.

❓ Predict Output

advanced

Output of Min Stack after mixed operations

What is printed after executing these operations on the Min Stack?

push(10), push(20), push(5), getMin(), pop(), getMin(), pop(), getMin()

DSA Java

MinStack ms = new MinStack();
ms.push(10);
ms.push(20);
ms.push(5);
System.out.print(ms.getMin() + ",");
ms.pop();
System.out.print(ms.getMin() + ",");
ms.pop();
System.out.print(ms.getMin());

A 5,10,10

B 5,10,20

C 10,10,10

D 20,10,5

💡 Hint

Track the minimum after each pop carefully.

After pushing 10,20,5 min is 5. Pop removes 5, min becomes 10. Pop removes 20, min remains 10.

🧠 Conceptual

expert

Optimal Min Stack Design for Space Efficiency

Which approach optimizes space usage in a Min Stack by storing minimum values only when they change?

A Store all elements in a linked list and scan for min on demand

B Store minimum for every element regardless of value

C Use a separate queue to track minimum values

D Push new minimum only if it is less than or equal to current min; pop min only if top equals current min

💡 Hint

Think about pushing minimum values only when they update.

Pushing minimum only when it changes reduces space by avoiding duplicates in min stack.

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