Min Stack Design in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Min Stack Operations

What is the output of the following sequence of operations on a Min Stack?

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

DSA C

struct MinStack {
    int stack[100];
    int minStack[100];
    int top;
    int minTop;
};

void push(struct MinStack* ms, int x) {
    ms->stack[++ms->top] = x;
    if (ms->minTop == -1 || x <= ms->minStack[ms->minTop]) {
        ms->minStack[++ms->minTop] = x;
    }
}

void pop(struct MinStack* ms) {
    if (ms->top == -1) return;
    int val = ms->stack[ms->top--];
    if (val == ms->minStack[ms->minTop]) {
        ms->minTop--;
    }
}

int getMin(struct MinStack* ms) {
    if (ms->minTop == -1) return -1;
    return ms->minStack[ms->minTop];
}

// Initial state: top = -1, minTop = -1
// Sequence:
// push(5), push(3), push(7), getMin(), pop(), getMin(), pop(), getMin()

A [5, 3, 5]

B [5, 5, 5]

C [3, 5, 5]

D [3, 3, 5]

💡 Hint

Remember the min stack keeps track of the smallest values so far.

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 a Secondary Stack in Min Stack Design?

Why do we use a secondary stack to keep track of minimum values in a Min Stack design?

A To keep track of the minimum values at each insertion for O(1) retrieval

B To reverse the order of elements for easier popping

C To store all elements in sorted order for quick access

D To reduce the overall memory usage by storing only minimum elements

💡 Hint

Think about how to get the minimum value quickly without scanning all elements.

The secondary stack stores the minimum value at each point so getMin() can return in constant time.

🔧 Debug

advanced

Identify the Bug in Min Stack Pop Operation

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

DSA C

void pop(struct MinStack* ms) {
    int val = ms->stack[ms->top--];
    if (val == ms->minStack[ms->minTop]) {
        ms->minTop--;
    }
}

A Accessing stack[-1] causes undefined behavior or crash

B No error, pop works correctly even if stack is empty

C minTop will never decrease causing incorrect minimum

D Stack top will not update correctly causing infinite loop

💡 Hint

What happens if top is -1 and you try to access stack[top]?

If the stack is empty (top == -1), accessing stack[top--] reads invalid memory causing undefined behavior.

❓ Predict Output

advanced

Resulting Stack and Min Stack States

After performing these operations on an empty Min Stack:
push(2), push(2), push(1), pop(), getMin(), pop(), getMin()
What is the final printed output of getMin calls?

DSA C

struct MinStack {
    int stack[100];
    int minStack[100];
    int top;
    int minTop;
};

// Assume push, pop, getMin as defined previously

// Operations:
// push(2), push(2), push(1), pop(), getMin(), pop(), getMin()

A [1, 2]

B [2, 2]

C [2, 1]

D [1, 1]

💡 Hint

Remember that duplicate minimum values are stored separately in min stack.

After pushing 2,2,1 and popping once, min is 2. After popping again, min remains 2 because of duplicate 2s.

🚀 Application

expert

Design Challenge: Min Stack with Constant Space

Which approach allows implementing a Min Stack that uses only one stack and constant extra space for tracking minimum values?

A Keep a sorted array alongside the stack to track minimums

B Use a linked list to store minimum values separately

C Store the difference between current value and minimum in the stack and update minimum accordingly

D Use two stacks, one for values and one for minimums

💡 Hint

Think about encoding minimum information within the stack elements themselves.

Storing differences allows tracking minimum with only one stack and constant extra space by encoding minimum info.