Stock Span Problem Using Stack in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Stock Span Calculation for Given Prices

What is the output of the stock span array after running the given Go code with prices [100, 80, 60, 70, 60, 75, 85]?

DSA Go

package main

import "fmt"

type Stack []int

func (s *Stack) Push(v int) {
    *s = append(*s, v)
}

func (s *Stack) Pop() int {
    if len(*s) == 0 {
        return -1
    }
    index := (*s)[len(*s)-1]
    *s = (*s)[:len(*s)-1]
    return index
}

func (s *Stack) Top() int {
    if len(*s) == 0 {
        return -1
    }
    return (*s)[len(*s)-1]
}

func calculateSpan(prices []int) []int {
    n := len(prices)
    span := make([]int, n)
    var s Stack

    for i := 0; i < n; i++ {
        for len(s) > 0 && prices[s.Top()] <= prices[i] {
            s.Pop()
        }
        if len(s) == 0 {
            span[i] = i + 1
        } else {
            span[i] = i - s.Top()
        }
        s.Push(i)
    }
    return span
}

func main() {
    prices := []int{100, 80, 60, 70, 60, 75, 85}
    span := calculateSpan(prices)
    fmt.Println(span)
}

A [1, 1, 1, 2, 1, 4, 6]

B [1, 1, 1, 1, 1, 1, 1]

C [1, 2, 3, 4, 5, 6, 7]

D [1, 1, 2, 2, 2, 3, 4]

💡 Hint

Remember the span counts how many consecutive days before the current day had prices less than or equal to the current price.

The stock span for each day is calculated by counting how many consecutive previous days had prices less than or equal to the current day's price. Using a stack to track indices of days with higher prices helps efficiently compute this.

🧠 Conceptual

intermediate

Understanding Stack Usage in Stock Span Problem

Why is a stack used in the stock span problem instead of a simple loop checking all previous days?

A Because stack stores all prices in sorted order automatically.

B Because stack allows us to efficiently find the previous higher price day in O(n) time.

C Because stack duplicates the array to avoid modifying the original prices.

D Because stack is used to reverse the prices array before processing.

💡 Hint

Think about how to avoid checking all previous days repeatedly.

The stack stores indices of days with prices higher than the current day, allowing us to jump directly to the last higher price day and avoid repeated comparisons, achieving O(n) time complexity.

🔧 Debug

advanced

Identify the Error in Stock Span Stack Implementation

What error will the following Go code produce when calculating stock span for prices [10, 4, 5, 90, 120, 80]? func calculateSpan(prices []int) []int { n := len(prices) span := make([]int, n) var s Stack for i := 0; i < n; i++ { for len(s) > 0 && prices[s.Top()] < prices[i] { s.Pop() } if len(s) == 0 { span[i] = i } else { span[i] = i - s.Top() } s.Push(i) } return span }

A The code will panic due to popping from an empty stack.

B The code will run correctly and produce the expected span array.

C The code will produce a syntax error because of missing parentheses.

D The span for the first day is zero instead of one, causing incorrect output.

💡 Hint

Check the span assignment when the stack is empty.

The span for the first day should be 1 (the day itself), but the code assigns i (which is 0), so the span is zero, which is incorrect.

🚀 Application

advanced

Applying Stock Span Logic to Find Maximum Span Day

Given the prices array [31, 27, 14, 21, 30, 22, 35], which day (0-based index) has the maximum stock span?

A 3

B 4

C 6

D 0

💡 Hint

Calculate the span array first, then find the index with the largest span value.

The maximum span corresponds to the longest consecutive days with prices less or equal to the current day. Day 6 has the highest price and the longest span.

❓ Predict Output

expert

Output of Stock Span with Repeated Prices

What is the output of the stock span array for prices [10, 10, 10, 10, 10] using the standard stack-based algorithm?

DSA Go

package main

import "fmt"

type Stack []int

func (s *Stack) Push(v int) {
    *s = append(*s, v)
}

func (s *Stack) Pop() int {
    if len(*s) == 0 {
        return -1
    }
    index := (*s)[len(*s)-1]
    *s = (*s)[:len(*s)-1]
    return index
}

func (s *Stack) Top() int {
    if len(*s) == 0 {
        return -1
    }
    return (*s)[len(*s)-1]
}

func calculateSpan(prices []int) []int {
    n := len(prices)
    span := make([]int, n)
    var s Stack

    for i := 0; i < n; i++ {
        for len(s) > 0 && prices[s.Top()] <= prices[i] {
            s.Pop()
        }
        if len(s) == 0 {
            span[i] = i + 1
        } else {
            span[i] = i - s.Top()
        }
        s.Push(i)
    }
    return span
}

func main() {
    prices := []int{10, 10, 10, 10, 10}
    span := calculateSpan(prices)
    fmt.Println(span)
}

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

B [1, 1, 1, 1, 1]

C [5, 4, 3, 2, 1]

D [1, 2, 1, 2, 1]

💡 Hint

Repeated equal prices increase the span count cumulatively.

Since all prices are equal, each day’s span includes all previous days plus itself, resulting in increasing spans from 1 to 5.

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