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

Recall & Review

beginner

What is a Min Stack?

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

beginner

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

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

intermediate

What happens when you push a new element smaller than the current minimum in a Min Stack?

You push the new element onto the main stack and also push it onto the min stack because it is 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 min stack.

beginner

Why do we need two stacks in Min Stack design?

One stack stores all elements, and the other keeps track of the minimum elements to allow quick access to the minimum at any time.

What does the extra stack in a Min Stack store?

A Minimum elements at each push

B All elements in sorted order

C Only the maximum elements

D Random elements

The extra stack stores the minimum element at each push to allow constant time retrieval.

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

A O(n)

B O(1)

C O(log n)

D O(n^2)

Pop operation is O(1) because it removes the top element from both stacks if needed.

If the new element is greater than the current minimum, what happens to the min stack when pushing?

A Clear the min stack

B Push the new element

C Push the current minimum again

D Do not push anything

We push the current minimum again to keep the min stack aligned with the main stack.

Which operation is NOT supported by a Min Stack?

A Sort all elements

B Pop

C Get minimum

D Push

Min Stack does not support sorting all elements; it only supports push, pop, top, and get minimum.

What is the space complexity of a Min Stack compared to a normal stack?

A Half the space

B Less space

C Same space

D Twice the space

Min Stack uses an extra stack to store minimums, so it uses roughly twice the space.

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

Think about how to keep track of minimum without scanning all elements.

Describe the advantages of using a Min Stack over a normal stack when minimum retrieval is needed.

Focus on time complexity and efficiency.

Practice

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

easy

A. To retrieve the minimum element in constant time

B. To sort elements in ascending order

C. To store elements in a queue fashion

D. To reverse the order of elements

Solution

1. Step 1: Understand Min Stack functionality

   A Min Stack is designed to keep track of the minimum element efficiently.

2. Step 2: Identify the key feature

   It allows retrieving the minimum element in constant time, unlike a normal stack.

3. Final Answer:

   To retrieve the minimum element in constant time -> Option A

4. Quick Check:

   Min Stack = Fast minimum retrieval [OK]

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

Common Mistakes:

• Thinking it sorts elements
• Confusing with queue behavior
• Assuming it reverses elements

2. Which of the following Go code snippets correctly declares a Min Stack struct with two slices for values and minimums?

easy

A. type MinStack struct { values map[int]int; mins []int }

B. type MinStack struct { values []int; min int }

C. type MinStack struct { values []int; mins []int }

D. type MinStack struct { values []int; mins int }

Solution

1. Step 1: Check struct fields for Min Stack

   Min Stack needs slices to store all values and track minimums at each push.

2. Step 2: Validate field types

   Both values and mins should be slices of int for stack behavior.

3. Final Answer:

   type MinStack struct { values []int; mins []int } -> Option C

4. Quick Check:

   Two int slices = correct Min Stack struct [OK]

Hint: Min Stack uses two int slices for values and mins [OK]

Common Mistakes:

• Using map instead of slice for values
• Using int instead of slice for mins
• Mixing types between fields

3. Given the following Go code for a Min Stack, what will be printed after the operations?

ms := MinStack{}
ms.Push(3)
ms.Push(5)
ms.Push(2)
ms.Push(1)
ms.Pop()
fmt.Println(ms.GetMin())

medium

A. 2

B. 1

C. 3

D. 5

Solution

1. Step 1: Trace Push operations and minimums

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

2. Step 2: Pop removes last pushed (1), so min updates to previous min (2)

   After pop, minimum is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Pop last min 1, new min = 2 [OK]

Hint: Pop removes last min, so min updates to previous min [OK]

Common Mistakes:

• Assuming min stays 1 after pop
• Confusing push order
• Not updating min stack on pop

4. Identify the bug in this Go Min Stack Pop method:

func (ms *MinStack) Pop() {
  ms.values = ms.values[:len(ms.values)-1]
  ms.mins = ms.mins[:len(ms.mins)]
}

medium

A. Pop method should return the popped value

B. The values slice is not shortened on pop

C. Pop method should clear both slices completely

D. The mins slice is not shortened on pop

Solution

1. Step 1: Analyze slice operations in Pop

   Values slice is shortened by one element correctly.

2. Step 2: Check mins slice operation

   Mins slice is sliced to full length, so it is not shortened, causing mismatch.

3. Final Answer:

   The mins slice is not shortened on pop -> Option D

4. Quick Check:

   mins slice must shrink with values [OK]

Hint: Pop must shrink both values and mins slices equally [OK]

Common Mistakes:

• Forgetting to shrink mins slice
• Assuming Pop returns value
• Clearing slices fully on pop

5. You want to design a Min Stack that supports Push, Pop, Top, and GetMin all in O(1) time. Which approach below correctly handles the minimum tracking when pushing a new element x?

hard

A. Push x to values; push x only if x < current min to mins

B. Push x to values; push min(x, current min) to mins

C. Push x to values; push current min only if x > current min to mins

D. Push x to values; do not update mins slice

Solution

1. Step 1: Understand min tracking logic

   Each push must record the minimum so far to allow O(1) GetMin.

2. Step 2: Compare new element with current min

   Push the smaller of x and current min onto mins slice to keep track.

3. Final Answer:

   Push x to values; push min(x, current min) to mins -> Option B

4. Quick Check:

   Always push min(x, current min) to mins [OK]

Hint: Always push min of new and current min to mins stack [OK]

Common Mistakes:

• Pushing x only if smaller causes missing mins
• Not updating mins on every push
• Ignoring mins slice updates