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.