Min Stack Design in DSA C

Mental Model

A Min Stack keeps track of the smallest value at every point so we can get the minimum quickly.

Analogy: Imagine a stack of plates where each plate also has a note showing the smallest plate size below it, so you always know the smallest plate without checking all plates.

Main Stack: 7 -> 3 -> 5 -> null
Min Stack: 3 -> 3 -> 5 -> null

Dry Run Walkthrough

Input: Push 5, Push 3, Push 7, GetMin, Pop, GetMin

Goal: Show how the Min Stack updates and returns the minimum value quickly after each operation

Step 1: Push 5 onto main stack and min stack

Main Stack: 5 -> null
Min Stack: 5 -> null

Why: First element is the minimum so far

Step 2: Push 3 onto main stack; compare with min stack top (5), push smaller (3) onto min stack

Main Stack: 3 -> 5 -> null
Min Stack: 3 -> 5 -> null

Why: 3 is smaller than previous min 5, so update min stack

Step 3: Push 7 onto main stack; compare with min stack top (3), push smaller (3) onto min stack

Main Stack: 7 -> 3 -> 5 -> null
Min Stack: 3 -> 3 -> 5 -> null

Why: 7 is not smaller than current min 3, so min stack keeps 3

Step 4: GetMin returns top of min stack (3)

Main Stack: 7 -> 3 -> 5 -> null
Min Stack: 3 -> 3 -> 5 -> null

Why: Top of min stack always holds current minimum

Step 5: Pop top from main stack (7) and min stack (3)

Main Stack: 3 -> 5 -> null
Min Stack: 3 -> 5 -> null

Why: Remove last pushed elements from both stacks to keep min stack synced

Step 6: GetMin returns top of min stack (3)

Main Stack: 3 -> 5 -> null
Min Stack: 3 -> 5 -> null

Why: Minimum remains 3 after popping 7

Result:

Main Stack: 3 -> 5 -> null
Min Stack: 3 -> 5 -> null
Minimum after operations: 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for stack
typedef struct Node {
    int val;
    struct Node* next;
} Node;

// Stack structure
typedef struct Stack {
    Node* top;
} Stack;

// Initialize stack
void initStack(Stack* s) {
    s->top = NULL;
}

// Push value onto stack
void push(Stack* s, int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->next = s->top;
    s->top = newNode;
}

// Pop value from stack
int pop(Stack* s) {
    if (s->top == NULL) return -1; // empty stack
    Node* temp = s->top;
    int val = temp->val;
    s->top = temp->next;
    free(temp);
    return val;
}

// Peek top value
int top(Stack* s) {
    if (s->top == NULL) return -1;
    return s->top->val;
}

// MinStack structure with two stacks
typedef struct MinStack {
    Stack mainStack;
    Stack minStack;
} MinStack;

// Initialize MinStack
void minStackInit(MinStack* ms) {
    initStack(&ms->mainStack);
    initStack(&ms->minStack);
}

// Push value onto MinStack
void minStackPush(MinStack* ms, int val) {
    push(&ms->mainStack, val); // push to main stack
    int currentMin = top(&ms->minStack);
    if (currentMin == -1 || val <= currentMin) {
        push(&ms->minStack, val); // push to min stack if smaller or equal
    } else {
        push(&ms->minStack, currentMin); // else push current min again
    }
}

// Pop from MinStack
void minStackPop(MinStack* ms) {
    pop(&ms->mainStack); // pop main stack
    pop(&ms->minStack);  // pop min stack to keep in sync
}

// Get minimum value
int minStackGetMin(MinStack* ms) {
    return top(&ms->minStack);
}

// Print stack from top to bottom
void printStack(Stack* s) {
    Node* curr = s->top;
    while (curr != NULL) {
        printf("%d -> ", curr->val);
        curr = curr->next;
    }
    printf("null\n");
}

int main() {
    MinStack ms;
    minStackInit(&ms);

    minStackPush(&ms, 5);
    minStackPush(&ms, 3);
    minStackPush(&ms, 7);

    printf("Main Stack: ");
    printStack(&ms.mainStack);
    printf("Min Stack: ");
    printStack(&ms.minStack);

    printf("Current Min: %d\n", minStackGetMin(&ms));

    minStackPop(&ms);

    printf("After pop:\n");
    printf("Main Stack: ");
    printStack(&ms.mainStack);
    printf("Min Stack: ");
    printStack(&ms.minStack);

    printf("Current Min: %d\n", minStackGetMin(&ms));

    return 0;
}

push(&ms->mainStack, val);

push value onto main stack to keep all elements

int currentMin = top(&ms->minStack);

get current minimum from min stack top

if (currentMin == -1 || val <= currentMin) { push(&ms->minStack, val); } else { push(&ms->minStack, currentMin); }

push new min or repeat current min to keep min stack synced

pop(&ms->mainStack); pop(&ms->minStack);

pop from both stacks to keep them aligned

return top(&ms->minStack);

return current minimum from min stack top

Output

Main Stack: 7 -> 3 -> 5 -> null

Min Stack: 3 -> 3 -> 5 -> null

Current Min: 3

After pop:

Main Stack: 3 -> 5 -> null

Min Stack: 3 -> 5 -> null

Current Min: 3

Complexity Analysis

Time: O(1) for push, pop, and getMin because all operations use only the top elements of stacks

Space: O(n) because we store all elements in main stack and a parallel min stack of same size

vs Alternative: Compared to scanning all elements to find min (O(n)), this design gives O(1) min retrieval at the cost of extra space

Edge Cases

Empty stack

Pop or getMin returns -1 or indicates empty safely

DSA C

if (s->top == NULL) return -1;

Push duplicate minimum values

Min stack stores duplicates to keep correct min after pops

DSA C

if (currentMin == -1 || val <= currentMin) { push(&ms->minStack, val); }

Pop until empty

Both stacks become empty and operations handle empty state gracefully

DSA C

if (s->top == NULL) return -1;

When to Use This Pattern

When a problem asks for a stack that can return the minimum value quickly at any time, use the Min Stack pattern to keep track of minimums alongside the main stack.

Common Mistakes

Mistake: Only pushing new minimum values onto min stack and not repeating current min for other pushes
Fix: Always push the smaller between new value and current min to min stack to keep stacks aligned

Mistake: Not popping from min stack when popping from main stack
Fix: Pop from both stacks simultaneously to keep min stack synced

Summary

Keeps track of minimum value in a stack with O(1) retrieval.

Use when you need fast minimum queries along with stack operations.

Store minimums in a parallel stack to track current minimum at each push.

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