Why Stock Span Problem Using Stack in DSA Go?

The Big Idea

Discover how a simple stack can save you hours of tedious price checking!

The Scenario

Imagine you are tracking daily stock prices on paper. For each day, you want to know how many consecutive previous days had prices less than or equal to today's price.

Doing this by checking every previous day manually for each new day is tiring and slow.

The Problem

Manually comparing each day's price with all previous days means repeating many checks again and again.

This wastes time and can cause mistakes, especially with many days of data.

The Solution

The Stock Span Problem uses a stack to remember important previous days efficiently.

This way, you quickly find how many days in a row had lower or equal prices without checking all days repeatedly.

Before vs After

✗ Before

for i := 0; i < len(prices); i++ {
    span := 1
    for j := i - 1; j >= 0 && prices[j] <= prices[i]; j-- {
        span++
    }
    spans[i] = span
}

✓ After

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

What It Enables

This method lets you find stock spans for many days quickly and accurately, even with thousands of prices.

Real Life Example

Traders use this to quickly understand how long a stock price has been rising or stable, helping them decide when to buy or sell.

Key Takeaways

Manual checking repeats work and is slow.

Stack remembers key days to speed up span calculation.

Efficiently solves the problem for large data sets.

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