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.

Practice

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

easy

A. To reverse the order of elements

B. To retrieve the minimum element in constant time

C. To store elements in a queue fashion

D. To sort elements in ascending order

Solution

1. Step 1: Understand Min Stack functionality

   A Min Stack is designed to allow retrieval of the minimum element quickly, usually in constant time.

2. Step 2: Compare with other options

   Sorting or queue behavior is not the main goal of a Min Stack; it focuses on minimum element retrieval.

3. Final Answer:

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

4. Quick Check:

   Min Stack = fast minimum retrieval [OK]

Hint: Min Stack always tracks minimum element fast [OK]

Common Mistakes:

• Confusing Min Stack with sorting algorithms
• Thinking it behaves like a queue
• Assuming it reverses elements

2. Which of the following is the correct way to declare a stack node structure for a Min Stack in C?

easy

A. typedef struct Node { int value; struct Node* next; int min; } Node;

B. typedef struct Node { int value; int min; } Node;

C. typedef struct Node { int value; struct Node* prev; } Node;

D. typedef struct Node { int value; struct Node* next; } Node;

Solution

1. Step 1: Identify required fields for Min Stack node

   A Min Stack node needs to store the value, a pointer to the next node, and the minimum value at that node.

2. Step 2: Match with options

   typedef struct Node { int value; struct Node* next; int min; } Node; includes value, next pointer, and min field, which is correct for Min Stack implementation.

3. Final Answer:

   typedef struct Node { int value; struct Node* next; int min; } Node; -> Option A

4. Quick Check:

   Node stores value, next, and min [OK]

Hint: Min Stack node needs value, next pointer, and min [OK]

Common Mistakes:

• Omitting the min field in node
• Using prev pointer instead of next
• Not using struct pointer for next

3. Consider the following C code snippet for a Min Stack push operation:

void push(Node** top, int x) {
    Node* newNode = malloc(sizeof(Node));
    newNode->value = x;
    if (*top == NULL) {
        newNode->min = x;
    } else {
        newNode->min = (x < (*top)->min) ? x : (*top)->min;
    }
    newNode->next = *top;
    *top = newNode;
}

What will be the minimum value after pushing elements 3, 5, 2 in this order on an empty stack?

medium

A. 2

B. 3

C. 5

D. Error

Solution

1. Step 1: Push 3 on empty stack

   Stack top is NULL, so min = 3.

2. Step 2: Push 5

   Compare 5 with current min 3; min remains 3.

3. Step 3: Push 2

   Compare 2 with current min 3; min updates to 2.

4. Final Answer:

   2 -> Option A

5. Quick Check:

   Minimum after pushes = 2 [OK]

Hint: Min updates only if new value is smaller [OK]

Common Mistakes:

• Not updating min on push
• Confusing min with last pushed value
• Assuming min resets on each push

4. The following C function is intended to pop an element from a Min Stack. Identify the error:

int pop(Node** top) {
    if (*top == NULL) return -1;
    int val = (*top)->value;
    free(*top);
    *top = (*top)->next;
    return val;
}

medium

A. Not checking if stack is empty

B. Returning value before freeing node

C. Accessing (*top)->next after freeing *top

D. Missing return statement

Solution

1. Step 1: Analyze order of operations

   The code frees *top, then accesses (*top)->next, which is invalid after free.

2. Step 2: Correct order

   Should save next pointer before freeing current node to avoid invalid access.

3. Final Answer:

   Accessing (*top)->next after freeing *top -> Option C

4. Quick Check:

   Free before next access causes error [OK]

Hint: Save next pointer before freeing node [OK]

Common Mistakes:

• Freeing node before accessing next
• Ignoring NULL check
• Returning value after free without saving

5. You want to design a Min Stack that supports push, pop, and getMin all in O(1) time using two stacks. Which approach correctly implements getMin?

hard

A. Use a queue to track minimum values

B. Sort the main stack on every push to keep minimum on top

C. Traverse the main stack on every getMin call to find minimum

D. Maintain a second stack that stores the minimum values; push new min or duplicate current min on push

Solution

1. Step 1: Understand two-stack Min Stack design

   One stack stores all values; the second stack keeps track of minimums for O(1) retrieval.

2. Step 2: Evaluate options

   Maintain a second stack that stores the minimum values; push new min or duplicate current min on push correctly describes pushing new minimum or current minimum duplicate onto second stack.

3. Final Answer:

   Maintain a second stack that stores the minimum values; push new min or duplicate current min on push -> Option D

4. Quick Check:

   Two stacks: one for values, one for mins [OK]

Hint: Use second stack to track mins for O(1) getMin [OK]

Common Mistakes:

• Sorting stack on every push (slow)
• Searching stack on getMin (not O(1))
• Using queue instead of stack