Stock Span Problem Using Stack in DSA C - Time & Space Complexity

Time Complexity: Stock Span Problem Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to solve the stock span problem changes as the number of days grows.

Specifically, how does the algorithm handle many stock prices efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void calculateSpan(int prices[], int n, int span[]) {
    int stack[n];
    int top = -1;

    for (int i = 0; i < n; i++) {
        while (top >= 0 && prices[stack[top]] < prices[i]) {
            top--;
        }
        span[i] = (top == -1) ? (i + 1) : (i - stack[top]);
        stack[++top] = i;
    }
}
    

This code calculates the stock span for each day using a stack to track previous higher prices.

Identify Repeating Operations

• Primary operation: The for-loop runs once for each day.
• Inside the loop: The while-loop pops from the stack while the current price is higher.
• How many times: Each element is pushed and popped at most once, so total stack operations are at most 2n.

How Execution Grows With Input

As the number of days increases, each price is processed once and compared with previous prices using the stack.

Input Size (n)	Approx. Operations
10	About 20 stack operations
100	About 200 stack operations
1000	About 2000 stack operations

Pattern observation: The total operations grow roughly in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to calculate spans grows directly with the number of days, making it efficient for large inputs.

Common Mistake

[X] Wrong: "The inner while-loop runs n times for each day, so the complexity is O(n²)."

[OK] Correct: Each price is pushed and popped only once, so total inner loop operations add up to n, not n times n.

Interview Connect

Understanding this problem shows you can use stacks to solve real-world challenges efficiently, a skill valued in many coding tasks.

Self-Check

"What if we used a simple nested loop without a stack? How would the time complexity change?"