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

Time Complexity: Stock Span Problem Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time taken grows when we calculate the stock span for many days.

How does the number of operations change as the list of stock prices gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def calculate_span(prices):
    stack = []  # stores indices
    span = [0] * len(prices)

    for i in range(len(prices)):
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    return span
    

This code calculates how many consecutive days before today the stock price was less or equal.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop runs once for each price.
• Inside loop: The while-loop pops from the stack, but each element is pushed and popped at most once.
• Dominant operation: The combined push and pop operations on the stack.

How Execution Grows With Input

Each price is processed once, and each index is pushed and popped at most once.

Input Size (n)	Approx. Operations
10	About 20 (10 pushes + up to 10 pops)
100	About 200 (100 pushes + up to 100 pops)
1000	About 2000 (1000 pushes + up to 1000 pops)

Pattern observation: Operations grow roughly in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows directly in proportion to the number of days.

Common Mistake

[X] Wrong: "The while-loop inside the for-loop makes this O(n²) because it can run many times each iteration."

[OK] Correct: Each element is pushed and popped only once, so total while-loop operations across all iterations add up to n, not n².

Interview Connect

Understanding this problem shows you can use stacks smartly to reduce repeated work, a skill useful in many coding challenges.

Self-Check

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