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

Time Complexity: Stock Span Problem Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to calculate stock spans changes as we get more stock prices.

How does the number of steps grow when we add more days of prices?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func calculateSpan(prices []int) []int {
    n := len(prices)
    span := make([]int, n)
    stack := []int{}

    for i := 0; i < n; i++ {
        for len(stack) > 0 && prices[stack[len(stack)-1]] <= prices[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            span[i] = i + 1
        } else {
            span[i] = i - stack[len(stack)-1]
        }
        stack = append(stack, i)
    }
    return span
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop runs once for each price (n times).
• Inner loop: The inner loop pops from the stack while the current price is higher than the top of the stack.
• How many times: Each element is pushed and popped at most once, so total inner loop operations across all iterations is at most n.

How Execution Grows With Input

As the number of prices (n) grows, the total steps grow roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 20 steps (each price pushed and popped once)
100	About 200 steps
1000	About 2000 steps

Pattern observation: The total work grows linearly with the number of prices.

Final Time Complexity

Time Complexity: O(n)

This means the time to calculate spans grows in direct proportion to the number of prices.

Common Mistake

[X] Wrong: "The inner loop runs n times for each price, so the time is O(n²)."

[OK] Correct: Each price is pushed and popped only once, so the inner loop total runs at most n times across all iterations, keeping time linear.

Interview Connect

Understanding this problem helps you see how stacks can optimize repeated comparisons, a useful skill for many coding challenges.

Self-Check

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

Practice

1. What does the stock span problem calculate for each day in a list of stock prices?

easy

A. The number of consecutive days before the current day with a price less than or equal to the current day's price

B. The maximum stock price in the entire list

C. The difference between the highest and lowest stock price

D. The total sum of stock prices up to the current day

Solution

1. Step 1: Understand the problem definition

   The stock span for a day is the count of consecutive previous days with prices less than or equal to that day's price.

2. Step 2: Clarify what is being calculated

   It is not about maximum price or sums, but about consecutive days with lower or equal prices.

3. Final Answer:

   The number of consecutive days before the current day with a price less than or equal to the current day's price -> Option A

4. Quick Check:

   Stock span = consecutive days with price ≤ current price [OK]

Hint: Span counts consecutive days with price ≤ current day price [OK]

Common Mistakes:

• Confusing span with maximum price
• Thinking span is total sum of prices
• Ignoring consecutive days condition

2. Which Go data structure is best suited to efficiently solve the stock span problem?

easy

A. Stack

B. Array

C. Queue

D. Map

Solution

1. Step 1: Identify the data structure for tracking previous prices

   The stack helps keep track of indices of days with prices to compare efficiently.

2. Step 2: Understand why stack is efficient

   Stack allows popping smaller prices and quickly finding the last higher price day, enabling O(n) time complexity.

3. Final Answer:

   Stack -> Option A

4. Quick Check:

   Stack is used for efficient previous price tracking [OK]

Hint: Use stack to track previous days' prices efficiently [OK]

Common Mistakes:

• Using array leads to O(n²) time
• Queue does not support backward checks
• Map is not suitable for order-based checks

3. What is the output span array for the stock prices [100, 80, 60, 70, 60, 75, 85] using the stock span algorithm?

medium

A. [1, 1, 2, 2, 3, 3, 4]

B. [1, 2, 3, 4, 5, 6, 7]

C. [1, 1, 1, 1, 1, 1, 1]

D. [1, 1, 1, 2, 1, 4, 6]

Solution

1. Step 1: Calculate span for each day

   Day 0: 100 -> span=1 (no previous)
   Day 1: 80 ≤ 100 -> span=1
   Day 2: 60 ≤ 80 -> span=1
   Day 3: 70 > 60 -> span=2 (includes day 2)
   Day 4: 60 ≤ 70 -> span=1
   Day 5: 75 > 60, 70 -> span=4 (includes days 4,3,2)
   Day 6: 85 > 75, 70, 60, 80 -> span=6 (includes days 5,4,3,2,1)

2. Step 2: Confirm final span array

   The spans are [1, 1, 1, 2, 1, 4, 6].

3. Final Answer:

   [1, 1, 1, 2, 1, 4, 6] -> Option D

4. Quick Check:

   Span array matches calculated values [OK]

Hint: Pop smaller prices from stack to count span [OK]

Common Mistakes:

• Counting all previous days instead of consecutive
• Not popping smaller prices from stack
• Confusing span with price values

4. Identify the bug in this Go code snippet for stock span calculation:

func calculateSpan(prices []int) []int {
    n := len(prices)
    span := make([]int, n)
    stack := []int{}
    for i := 0; i < n; i++ {
        for len(stack) > 0 && prices[stack[len(stack)-1]] <= prices[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            span[i] = i + 1
        } else {
            span[i] = i - stack[len(stack)-1]
        }
        stack = append(stack, i)
    }
    return span
}

medium

A. The loop should start from i = 1 instead of 0

B. The comparison operator should be <= instead of < in the inner loop

C. Span array is not initialized with correct size

D. Stack should store prices, not indices

Solution

1. Step 1: Analyze the inner loop condition

   The inner loop pops indices while the price at stack top is less than current price. It should pop while less than or equal to handle equal prices correctly.

2. Step 2: Understand impact of using < instead of <=

   Using < misses popping equal prices, causing incorrect span counts for equal prices.

3. Final Answer:

   The comparison operator should be <= instead of < in the inner loop -> Option B

4. Quick Check:

   Use <= to correctly handle equal prices [OK]

Hint: Use <= in comparison to handle equal prices correctly [OK]

Common Mistakes:

• Stack storing prices instead of indices
• Incorrect span array size
• Starting loop from wrong index

5. Given stock prices [10, 4, 5, 90, 120, 80], how would you modify the stock span algorithm to also return the day index of the last higher price before the current day? What is the output for the last higher price indices array?

hard

A. [ -1, 0, 1, -1, -1, 4 ]

B. [ -1, 0, 0, 2, 3, 3 ]

C. [-1, 0, 0, -1, -1, 4]

D. [ 0, -1, 1, 2, 3, 4 ]

Solution

1. Step 1: Modify algorithm to track last higher price index

   Use stack to store indices; for each day, pop while current price ≥ price at stack top. If stack empty, last higher index is -1; else top of stack is last higher index.

2. Step 2: Calculate last higher price indices for given prices

   Prices: [10,4,5,90,120,80]
   Day 0: empty -> -1
   Day 1: 10 > 4, no pop -> 0
   Day 2: 4 <= 5 pop 1, 10 > 5 -> 0
   Day 3: 5 <= 90 pop 2, 10 <= 90 pop 0, empty -> -1
   Day 4: 90 <= 120 pop 3, empty -> -1
   Day 5: 120 > 80, no pop -> 4

3. Final Answer:

   [-1, 0, 0, -1, -1, 4] -> Option C

4. Quick Check:

   Last higher indices track previous greater price day [OK]

Hint: Track last higher price index using stack top or -1 if empty [OK]

Common Mistakes:

• Returning span instead of last higher index
• Not handling empty stack case (-1)
• Confusing last higher index with span count