Stock Span Problem Using Stack in DSA Go - Deep Dive

Overview - Stock Span Problem Using Stack

What is it?

The Stock Span Problem is about finding how many consecutive days before today the stock price was less than or equal to today's price. We use a stack to efficiently track these days and calculate the span for each day. This helps in understanding stock price trends quickly without checking all previous days every time.

Why it matters

Without this method, checking stock spans would be slow because you'd have to look back at every previous day for each new price. This would waste time and computing power, especially with many days of data. Using a stack makes the process fast and practical for real-world stock analysis and decision-making.

Where it fits

Before learning this, you should understand basic arrays and stacks. After this, you can explore other stack problems like Next Greater Element or advanced data structures for financial data analysis.

Mental Model

Core Idea

Use a stack to remember days with higher stock prices so you can quickly find how far back prices were lower or equal.

Think of it like...

Imagine a line of people waiting to buy tickets, where each person only cares about how many people in front have shorter or equal height. The stack helps keep track of these taller people so you don't have to check everyone every time.

Day:    1    2    3    4    5    6    7
Price:  100  80   60   70   60   75   85
Stack:  [1]  [1]  [1]  [1,3] [1,3] [1,6] [1,7]
Span:   1    1    1    2    1    4    6

Build-Up - 7 Steps

1

Foundation

Understanding Stock Span Concept

Concept: Learn what the stock span means and how it relates to previous days' prices.

The stock span for a day is the count of consecutive days before it where the price was less than or equal to the current day's price. For example, if today's price is 75 and yesterday's was 70, and the day before was 60, the span is 3 because all three days had prices less or equal to 75.

Result

You understand that span measures how long the price has been rising or stable.

Understanding the span concept is key to knowing why we need an efficient way to find how many previous days meet the condition.

2

Foundation

Basics of Stack Data Structure

Concept: Learn what a stack is and how it works with push and pop operations.

A stack is like a stack of plates: you add (push) plates on top and remove (pop) from the top only. It follows Last In First Out (LIFO). This helps us keep track of days in order and quickly remove days that don't meet our condition.

Result

You can use a stack to store days and their prices to help calculate spans.

Knowing stack operations prepares you to use it for efficient span calculation instead of checking all previous days.

3

Intermediate

Naive Span Calculation Approach

🤔Before reading on: Do you think checking all previous days for each price is efficient or slow? Commit to your answer.

Concept: Calculate span by checking each previous day until a higher price is found.

For each day, start from the previous day and move backward until you find a day with a higher price. Count how many days you passed. This works but is slow for large data because it may check many days repeatedly.

Result

Span for each day is correct but calculation time grows quickly with more days.

Understanding the naive method shows why we need a better approach to avoid repeated checks.

4

Intermediate

Using Stack to Optimize Span Calculation

🤔Before reading on: Do you think a stack can help skip checking all previous days? Commit to your answer.

Concept: Use a stack to keep track of days with prices higher than the current day to jump over multiple days at once.

We push days onto the stack if their price is higher than the current day's price. When a new price comes, we pop days from the stack while their prices are less or equal to the current price. The span is the difference between current day and the day on top of the stack after popping.

Result

Span calculation becomes much faster, often O(n) for n days.

Using a stack cleverly skips unnecessary checks, making the algorithm efficient.

5

Intermediate

Implementing Stack-Based Span in Go

Concept: Write Go code that uses a stack to calculate stock spans for a list of prices.

We create a stack to store indices of days. For each price, pop from stack while top price is less or equal. If stack is empty, span is current day + 1; else span is difference between current day and top of stack. Push current day index onto stack.

Result

The program outputs the span array for given prices.

Implementing the algorithm solidifies understanding and shows practical use of stacks.

6

Advanced

Handling Edge Cases and Large Inputs

🤔Before reading on: Do you think the stack approach handles all edge cases like equal prices or single day? Commit to your answer.

Concept: Consider cases like all prices equal, strictly increasing or decreasing prices, and very large input sizes.

The stack approach naturally handles equal prices by popping them, ensuring correct spans. For large inputs, the O(n) time complexity ensures performance. Single day input returns span 1. Testing these cases confirms robustness.

Result

The algorithm works correctly and efficiently for all edge cases.

Knowing how the algorithm behaves in edge cases prevents bugs and ensures reliability.

7

Expert

Memory and Performance Optimizations

🤔Before reading on: Can you think of ways to reduce memory or improve speed beyond the basic stack approach? Commit to your answer.

Concept: Explore reducing memory by reusing arrays, minimizing stack operations, and understanding amortized time complexity.

We can reuse the input array to store spans to save memory. The stack operations are amortized O(1) because each element is pushed and popped once. Understanding this helps optimize implementations in production systems.

Result

Optimized code uses less memory and runs efficiently even on huge datasets.

Understanding amortized analysis and memory reuse leads to better real-world implementations.

Under the Hood

The stack stores indices of days with strictly higher prices. When a new price arrives, the algorithm pops all indices with prices less or equal to current price, effectively skipping those days. The span is calculated by subtracting the index of the last higher price day from the current day index. This ensures each day is pushed and popped at most once, making the algorithm O(n).

Why designed this way?

The problem requires checking previous days efficiently. A naive approach is O(n²). Using a stack exploits the property that prices form a sequence where only the last higher price matters for span calculation. This design reduces redundant comparisons and improves performance drastically.

Prices:  100   80   60   70   60   75   85
Index:    0     1    2    3    4    5    6
Stack:   ┌────┐
         │ 0  │  (price 100)
         └────┘
Day 1 price 80 < 100, push 1
Stack:   ┌────┐
         │ 1  │
         │ 0  │
         └────┘
Day 2 price 60 < 80, push 2
Stack:   ┌────┐
         │ 2  │
         │ 1  │
         │ 0  │
         └────┘
Day 3 price 70 > 60, pop 2
Day 3 price 70 < 80, push 3
Stack:   ┌────┐
         │ 3  │
         │ 1  │
         │ 0  │
         └────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the stack store prices or indices? Commit to your answer.

Common Belief: The stack stores the actual stock prices to compare directly.

Reality: The stack stores indices of days, not prices, to calculate spans using positions.

Why it matters: Storing prices instead of indices makes it impossible to calculate spans correctly because you need day positions to find the span length.

Quick: Is the time complexity of the stack approach O(n²)? Commit to your answer.

Common Belief: Because we pop elements, the algorithm might be O(n²) in the worst case.

Reality: Each element is pushed and popped at most once, so the time complexity is O(n).

Why it matters: Believing it's slower may discourage using this efficient method in real applications.

Quick: Does the algorithm fail if prices are equal on consecutive days? Commit to your answer.

Common Belief: Equal prices cause incorrect span calculation because the stack only handles strictly greater prices.

Reality: The algorithm correctly handles equal prices by popping them, ensuring spans count consecutive days with less or equal prices.

Why it matters: Misunderstanding this leads to incorrect implementations that fail on equal price sequences.

Quick: Can we use a queue instead of a stack for this problem? Commit to your answer.

Common Belief: A queue can be used because it also stores elements in order.

Reality: A queue does not support the needed last-in-first-out behavior to efficiently find the last higher price day.

Why it matters: Using a queue leads to inefficient or incorrect solutions because it cannot skip days properly.

Expert Zone

1

The stack approach's amortized O(1) pop and push operations mean that even though some days cause multiple pops, overall performance stays linear.

2

Reusing the input array to store spans can save memory but requires careful handling to avoid overwriting needed data during computation.

3

In real trading systems, this algorithm can be adapted to streaming data by maintaining the stack state across incoming prices.

When NOT to use

If you need spans based on complex conditions beyond simple price comparisons, such as volume or multi-factor criteria, this stack approach won't work. Instead, use segment trees or binary indexed trees for range queries.

Production Patterns

In production, this algorithm is used in financial analytics dashboards to quickly show stock trends. It is often combined with real-time data feeds and optimized with memory pools and concurrency controls.

Connections

Next Greater Element Problem

Builds-on and similar pattern

Understanding the stock span problem helps grasp the Next Greater Element problem because both use stacks to find the next or previous higher value efficiently.

Amortized Analysis in Algorithms

Builds-on concept

Knowing how each element is pushed and popped once explains why the algorithm runs in linear time, illustrating amortized analysis principles.

Human Queue Management

Analogy from real life

The way the stack skips over days with lower prices is like a manager quickly letting taller people ahead in line, showing how data structures mimic real-world prioritization.

Common Pitfalls

#1 Pushing prices instead of indices on the stack.

Wrong approach:

stack := []int{}
for i, price := range prices {
for len(stack) > 0 && prices[stack[len(stack)-1]] <= price {
stack = stack[:len(stack)-1]
}
stack = append(stack, price) // wrong: pushing price instead of index
}

Correct approach:

stack := []int{}
for i, price := range prices {
for len(stack) > 0 && prices[stack[len(stack)-1]] <= price {
stack = stack[:len(stack)-1]
}
stack = append(stack, i) // correct: pushing index
}

Root cause:

Confusing the need to track positions (indices) with the actual price values.

#2 Calculating span as current index minus popped index instead of top of stack index.

Wrong approach:

span[i] = i - poppedIndex // wrong calculation

Correct approach:

if len(stack) == 0 {
span[i] = i + 1
} else {
span[i] = i - stack[len(stack)-1]
}

Root cause:

Misunderstanding that the span depends on the last higher price day still on the stack, not the popped day.

#3 Not popping all smaller or equal prices before pushing current price.

Wrong approach:

for i, price := range prices {
if len(stack) == 0 || prices[stack[len(stack)-1]] > price {
stack = append(stack, i)
}
// missing popping loop
}

Correct approach:

for i, price := range prices {
for len(stack) > 0 && prices[stack[len(stack)-1]] <= price {
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}

Root cause:

Forgetting to remove all days with lower or equal prices leads to incorrect span calculation.

Key Takeaways

The Stock Span Problem measures how many consecutive previous days had prices less or equal to today's price.

Using a stack to store indices of days with higher prices allows efficient span calculation in linear time.

Each price is pushed and popped at most once, making the algorithm fast even for large datasets.

Correct span calculation depends on using indices, not prices, and popping all smaller or equal prices before pushing the current day.

Understanding this problem builds a foundation for solving many other stack-based sequence problems.

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