Min Stack Design in DSA C - Time & Space Complexity

Time Complexity: Min Stack Design

O(1)

Understanding Time Complexity

We want to understand how fast the Min Stack operations run as the number of elements grows.

Specifically, how does the time to push, pop, or get the minimum change with more items?

Scenario Under Consideration

Analyze the time complexity of the following Min Stack code snippet.

typedef struct {
    int *stack;
    int *minStack;
    int top;
    int capacity;
} MinStack;

void push(MinStack* obj, int val) {
    obj->stack[++obj->top] = val;
    int minVal = obj->top == 0 ? val : (val < obj->minStack[obj->top - 1] ? val : obj->minStack[obj->top - 1]);
    obj->minStack[obj->top] = minVal;
}

void pop(MinStack* obj) {
    if (obj->top >= 0) obj->top--;
}

int getMin(MinStack* obj) {
    return obj->minStack[obj->top];
}
    

This code keeps track of the minimum value at each stack level to allow quick minimum retrieval.

Identify Repeating Operations

Look for loops or repeated steps inside each operation.

• Primary operation: Each push, pop, and getMin runs a fixed number of steps without loops.
• How many times: Each operation runs once per call, no matter how many elements are in the stack.

How Execution Grows With Input

Each operation does a constant amount of work regardless of stack size.

Input Size (n)	Approx. Operations per push/pop/getMin
10	5-6 steps
100	5-6 steps
1000	5-6 steps

Pattern observation: The number of steps stays the same no matter how many elements are in the stack.

Final Time Complexity

Time Complexity: O(1)

This means each operation takes the same short time no matter how big the stack is.

Common Mistake

[X] Wrong: "Finding the minimum must scan all elements, so it takes longer as stack grows."

[OK] Correct: The min stack stores the minimum at each step, so getMin just reads one value instantly.

Interview Connect

Knowing how to keep track of minimum values efficiently shows your skill in designing smart data structures.

Self-Check

"What if we used only one stack and searched for the minimum each time getMin is called? How would the time complexity change?"