Min Stack Design in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to push an element onto the stack.

DSA Java

public void push(int x) {
    stack.[1](x);
}

Drag options to blanks, or click blank then click option'

Aempty

Bpop

Cpeek

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push will remove an element instead of adding.

Using peek only views the top element without adding.

The push method adds an element to the top of the stack.

2fill in blank

medium

Complete the code to get the minimum element from the min stack.

DSA Java

public int getMin() {
    return minStack.[1]();
}

Drag options to blanks, or click blank then click option'

Apeek

Bpush

Cpop

Dempty

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop removes the minimum element, which is incorrect here.

Using push or empty does not retrieve the minimum.

peek returns the top element without removing it, which is the current minimum.

3fill in blank

hard

Fix the error in the pop method to correctly update the min stack.

DSA Java

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

Drag options to blanks, or click blank then click option'

Apeek

Bempty

Cpush

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop removes the element, causing incorrect behavior.

Using push or empty is not suitable here.

We compare the top of the main stack with the top of the min stack using peek, not pop.

4fill in blank

hard

Fill both blanks to correctly update the min stack when pushing a new element.

DSA Java

public void push(int x) {
    stack.push(x);
    if(minStack.isEmpty() || x [1] minStack.[2]()) {
        minStack.push(x);
    }
}

Drag options to blanks, or click blank then click option'

A<=

B>

Cpeek

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<=' reverses the logic.

Using pop removes the minimum element incorrectly.

We check if x is less than or equal to the current minimum (peek) to update minStack.

5fill in blank

hard

Fill all three blanks to implement getMin method using minStack.

DSA Java

public int getMin() {
    return minStack.[1]();
}

public void push(int x) {
    stack.push(x);
    if(minStack.isEmpty() || x [2] minStack.[3]()) {
        minStack.push(x);
    }
}

Drag options to blanks, or click blank then click option'

Apop

B<=

Cpeek

Dempty

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop in getMin removes the minimum element.

Using '>' reverses the comparison logic.

getMin uses peek to view the minimum; push compares x <= minStack.peek() to update minStack.

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