Stock Span Problem Using Stack in DSA C

Mental Model

We want to find, for each day, how many consecutive days up to and including today had stock prices less than or equal to today's price. We use a stack to remember days with higher prices to quickly find the span.

Analogy: Imagine a line of people with different heights. For each person, you count how many consecutive people up to and including them (going backwards) are shorter or equal in height until you find a taller person. The stack helps you remember the taller people so you don't check everyone again.

Prices:  [100] [80] [60] [70] [60] [75] [85]
Index:    0     1    2    3    4    5    6
Stack:   Top -> [index of days with higher price]
Span:    [1]  [1]  [1]  [2]  [1]  [4]  [6]

Dry Run Walkthrough

Input: prices: [100, 80, 60, 70, 60, 75, 85]

Goal: Calculate the stock span for each day, which is how many consecutive days up to and including the current day had price less than or equal to current day's price

Step 1: Start with day 0, price 100, stack empty, push day 0

Stack: [0]
Span: [1]

Why: First day always has span 1 because no previous days

Step 2: Day 1, price 80, top of stack day 0 price 100 > 80, push day 1

Stack: [0, 1]
Span: [1, 1]

Why: Price 80 is less than 100, so span is 1

Step 3: Day 2, price 60, top stack day 1 price 80 > 60, push day 2

Stack: [0, 1, 2]
Span: [1, 1, 1]

Why: Price 60 less than 80, span 1

Step 4: Day 3, price 70, pop day 2 (60 <= 70), now top day 1 price 80 > 70, push day 3

Stack: [0, 1, 3]
Span: [1, 1, 1, 2]

Why: Popped day 2 (60 <= 70); span = 2 (days 2 and 3)

Step 5: Day 4, price 60, top day 3 price 70 > 60, push day 4

Stack: [0, 1, 3, 4]
Span: [1, 1, 1, 2, 1]

Why: Price 60 less than 70, span 1

Step 6: Day 5, price 75, pop day 4 (60 <= 75), pop day 3 (70 <= 75), top day 1 price 80 > 75, push day 5

Stack: [0, 1, 5]
Span: [1, 1, 1, 2, 1, 4]

Why: Popped days 4 and 3; span = 4 (days 2, 3, 4, 5)

Step 7: Day 6, price 85, pop day 5 (75 <= 85), pop day 1 (80 <= 85), top day 0 price 100 > 85, push day 6

Stack: [0, 6]
Span: [1, 1, 1, 2, 1, 4, 6]

Why: Popped days 5 and 1; span = 6 (days 1, 2, 3, 4, 5, 6)

Result:

Final span array: [1, 1, 1, 2, 1, 4, 6]

Annotated Code

DSA C

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

// Stack structure to hold indices
typedef struct Stack {
    int *arr;
    int top;
    int capacity;
} Stack;

// Create stack
Stack* createStack(int capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->arr = (int*)malloc(capacity * sizeof(int));
    return stack;
}

// Check if stack is empty
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// Push to stack
void push(Stack *stack, int val) {
    stack->arr[++stack->top] = val;
}

// Pop from stack
int pop(Stack *stack) {
    return stack->arr[stack->top--];
}

// Peek top of stack
int peek(Stack *stack) {
    return stack->arr[stack->top];
}

// Calculate stock span
void calculateSpan(int prices[], int n, int span[]) {
    if (n == 0) return; // handle empty array gracefully
    Stack *stack = createStack(n);

    // First day span is always 1
    span[0] = 1;
    push(stack, 0); // push index 0

    for (int i = 1; i < n; i++) {
        // Pop indices while price at stack top <= current price
        while (!isEmpty(stack) && prices[peek(stack)] <= prices[i]) {
            pop(stack); // remove smaller or equal prices
        }

        // If stack empty, span is i+1 else difference
        span[i] = isEmpty(stack) ? (i + 1) : (i - peek(stack));

        push(stack, i); // push current index
    }

    free(stack->arr);
    free(stack);
}

int main() {
    int prices[] = {100, 80, 60, 70, 60, 75, 85};
    int n = sizeof(prices) / sizeof(prices[0]);
    int span[n];

    calculateSpan(prices, n, span);

    for (int i = 0; i < n; i++) {
        printf("%d ", span[i]);
    }
    printf("\n");

    return 0;
}

span[0] = 1; push(stack, 0);

Initialize first day span and push its index

while (!isEmpty(stack) && prices[peek(stack)] <= prices[i]) { pop(stack); }

Pop indices with prices less or equal to current price to find last higher price

span[i] = isEmpty(stack) ? (i + 1) : (i - peek(stack));

Calculate span based on distance to last higher price or whole range if none

push(stack, i);

Push current day index for future comparisons

Output

1 1 1 2 1 4 6 

Complexity Analysis

Time: O(n) because each element is pushed and popped at most once

Space: O(n) for the stack and span array to store indices and results

vs Alternative: Naive approach is O(n^2) by checking all previous days for each day, stack reduces it to O(n)

Edge Cases

Empty price array

No spans calculated, function handles gracefully

DSA C

if (n == 0) return; in calculateSpan

All prices equal

Span increases by 1 each day because all previous prices are <= current

DSA C

while (!isEmpty(stack) && prices[peek(stack)] <= prices[i]) { pop(stack); }

Strictly decreasing prices

Span is always 1 because no previous price is less or equal

DSA C

while condition fails immediately, span[i] = 1

When to Use This Pattern

When asked to find how many previous consecutive elements satisfy a condition relative to current, use a stack to track indices for O(n) solution.

Common Mistakes

Mistake: Not popping all smaller or equal prices from stack before calculating span
Fix: Use a while loop to pop until top price is greater than current

Mistake: Calculating span as difference between indices without checking if stack is empty
Fix: Check if stack is empty; if yes, span is current index + 1

Summary

Calculates how many consecutive days up to and including the current day had stock prices less than or equal to current day's price using a stack.

Use when you need to find spans or counts of consecutive elements satisfying a condition efficiently.

The key is to use a stack to remember indices of days with higher prices to quickly find the span.