Min Stack Design in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Min Stack after Push and Pop Operations

Consider a Min Stack that supports push, pop, and getMin operations. What is the output of the getMin() calls after the following operations?

push(5), push(3), push(7), getMin(), pop(), getMin(), pop(), getMin()

DSA Go

package main

import "fmt"

type MinStack struct {
    stack []int
    minStack []int
}

func (ms *MinStack) Push(x int) {
    ms.stack = append(ms.stack, x)
    if len(ms.minStack) == 0 || x <= ms.minStack[len(ms.minStack)-1] {
        ms.minStack = append(ms.minStack, x)
    }
}

func (ms *MinStack) Pop() {
    if len(ms.stack) == 0 {
        return
    }
    top := ms.stack[len(ms.stack)-1]
    ms.stack = ms.stack[:len(ms.stack)-1]
    if top == ms.minStack[len(ms.minStack)-1] {
        ms.minStack = ms.minStack[:len(ms.minStack)-1]
    }
}

func (ms *MinStack) GetMin() int {
    if len(ms.minStack) == 0 {
        return -1
    }
    return ms.minStack[len(ms.minStack)-1]
}

func main() {
    ms := MinStack{}
    ms.Push(5)
    ms.Push(3)
    ms.Push(7)
    fmt.Println(ms.GetMin())
    ms.Pop()
    fmt.Println(ms.GetMin())
    ms.Pop()
    fmt.Println(ms.GetMin())
}

A [3, 3, 5]

B [5, 3, 5]

C [3, 5, 5]

D [5, 5, 5]

💡 Hint

Remember the minStack keeps track of the minimum values at each push.

After pushing 5, 3, 7, the minimum is 3. After popping 7, minimum remains 3. After popping 3, minimum becomes 5.

🧠 Conceptual

intermediate

Why Use an Auxiliary Stack in Min Stack Design?

Why do we use a separate stack (minStack) alongside the main stack in a Min Stack implementation?

A To store duplicate elements separately for memory optimization.

B To store all elements in sorted order for quick access.

C To reverse the order of elements for pop operations.

D To keep track of the minimum element at each state for O(1) retrieval.

💡 Hint

Think about how to get the minimum element quickly without scanning the whole stack.

The auxiliary stack stores the minimum element at each push so getMin() can return in constant time.

🔧 Debug

advanced

Identify the Bug in Min Stack Pop Method

What error will occur when running this Pop method of Min Stack?

func (ms *MinStack) Pop() {
    top := ms.stack[len(ms.stack)-1]
    ms.stack = ms.stack[:len(ms.stack)-1]
    if top == ms.minStack[len(ms.minStack)-1] {
        ms.minStack = ms.minStack[:len(ms.minStack)-1]
    }
}

A No error, works correctly

B Runtime panic: index out of range when stack is empty

C Compilation error: missing return statement

D Runtime panic: nil pointer dereference

💡 Hint

What happens if Pop is called on an empty stack?

The method does not check if the stack is empty before accessing the last element, causing an index out of range panic.

❓ Predict Output

advanced

Output of Min Stack after Complex Push and Pop Sequence

What is the output of the getMin() calls after this sequence?

push(2), push(0), push(3), push(0), getMin(), pop(), getMin(), pop(), getMin(), pop(), getMin()

DSA Go

package main

import "fmt"

type MinStack struct {
    stack []int
    minStack []int
}

func (ms *MinStack) Push(x int) {
    ms.stack = append(ms.stack, x)
    if len(ms.minStack) == 0 || x <= ms.minStack[len(ms.minStack)-1] {
        ms.minStack = append(ms.minStack, x)
    }
}

func (ms *MinStack) Pop() {
    if len(ms.stack) == 0 {
        return
    }
    top := ms.stack[len(ms.stack)-1]
    ms.stack = ms.stack[:len(ms.stack)-1]
    if top == ms.minStack[len(ms.minStack)-1] {
        ms.minStack = ms.minStack[:len(ms.minStack)-1]
    }
}

func (ms *MinStack) GetMin() int {
    if len(ms.minStack) == 0 {
        return -1
    }
    return ms.minStack[len(ms.minStack)-1]
}

func main() {
    ms := MinStack{}
    ms.Push(2)
    ms.Push(0)
    ms.Push(3)
    ms.Push(0)
    fmt.Println(ms.GetMin())
    ms.Pop()
    fmt.Println(ms.GetMin())
    ms.Pop()
    fmt.Println(ms.GetMin())
    ms.Pop()
    fmt.Println(ms.GetMin())
}

A [0, 0, 0, 2]

B [0, 0, 2, 2]

C [0, 3, 2, 2]

D [2, 0, 0, 2]

💡 Hint

Track the minimum after each pop carefully.

The minimum stays 0 until the last pop, then it becomes 2.

🚀 Application

expert

Minimum Number of Operations to Maintain Min Stack

Given a sequence of n push and pop operations on a Min Stack, what is the minimum number of times the auxiliary minStack is updated (push or pop) to maintain correct minimum tracking?

A At most n times, once per push or pop operation

B Exactly n times, always updated on every push and pop

C At most 2n times, because minStack updates can happen on both push and pop

D At most n/2 times, only when minimum changes

💡 Hint

Consider that minStack updates happen on some pushes and some pops.

Each push can add to minStack if new min, and each pop can remove from minStack if top equals min. So total updates can be up to 2n.

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