Stock Span Problem Using Stack in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a stack of integers in Go.

DSA Go

var stack [][1]

Drag options to blanks, or click blank then click option'

Abool

Bstring

Cfloat64

Dint

Attempts:

3 left

💡 Hint

Common Mistakes

Using string or float64 instead of int for the stack type.

We use int type for the stack because we store indices of prices, which are integers.

2fill in blank

medium

Complete the code to push an element onto the stack.

DSA Go

stack = append(stack, [1])

Drag options to blanks, or click blank then click option'

Ai

Blen(stack)

Cstack[0]

Dpop()

Attempts:

3 left

💡 Hint

Common Mistakes

Appending length or popping instead of adding the index.

We append the current i to the stack to push it.

3fill in blank

hard

Fix the error in the condition to pop from stack while top price is less or equal to current price.

DSA Go

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

Drag options to blanks, or click blank then click option'

A+1

B-1

C0

D-2

Attempts:

3 left

💡 Hint

Common Mistakes

Using +1 or 0 causes index out of range or wrong element.

We use len(stack)-1 to access the top element of the stack.

4fill in blank

hard

Fill both blanks to calculate the span when stack is empty or not empty.

DSA Go

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

Drag options to blanks, or click blank then click option'

Ai + 1

BstackTopIndex

C0

Dstack[len(stack)-1]

Attempts:

3 left

💡 Hint

Common Mistakes

Using zero or wrong index for span calculation.

If stack is empty, span is i + 1. Otherwise, span is difference between current index and top stack index stack[len(stack)-1].

5fill in blank

hard

Fill all three blanks to complete the stock span function using stack.

DSA Go

func calculateSpan(prices []int) []int {
    n := len(prices)
    span := make([]int, n)
    var 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] = [2]
        } else {
            span[i] = i - [3]
        }
        stack = append(stack, i)
    }
    return span
}

Drag options to blanks, or click blank then click option'

A-1

Bi + 1

Cstack[len(stack)-1]

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Wrong index access causing runtime error.

Incorrect span calculation when stack is empty.

We access top stack index with len(stack)-1 (blank 1 as -1). If stack empty, span is i+1 (blank 2). Otherwise, span is i - stack[len(stack)-1] (blank 3).

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