Stock Span Problem Using Stack in DSA Typescript - Build from Scratch

Stock Span Problem Using Stack

📖 Scenario: You are working as a stock analyst. You want to find out how many consecutive days before today the stock price was less than or equal to today's price. This helps in understanding the stock's performance trend.

🎯 Goal: Build a program that calculates the stock span for each day using a stack. The stock span is the number of consecutive days the price was less than or equal to the current day's price.

📋 What You'll Learn

Create an array called prices with the exact values: [100, 80, 60, 70, 60, 75, 85]

Create a stack called stack to store indices of days

Create an array called span to store the span values for each day

Use a for loop with variable i to iterate over prices

Inside the loop, use a while loop to pop from stack while the price at the top index is less than or equal to the current price

Calculate the span for each day and store it in span[i]

Print the span array at the end

💡 Why This Matters

🌍 Real World

Stock analysts use the stock span problem to quickly understand how long a stock price has been rising or stable, helping in making investment decisions.

💼 Career

This problem teaches stack usage, which is important for many technical interviews and real-world applications involving previous state comparisons.

1

Create the stock prices array

Create an array called prices with these exact values: [100, 80, 60, 70, 60, 75, 85]

DSA Typescript

# Create the prices array
# Your code here

Hint

Use const prices = [100, 80, 60, 70, 60, 75, 85]; to create the array.

2

Initialize stack and span array

Create an empty array called stack to use as a stack and an array called span with the same length as prices filled with zeros

DSA Typescript

const prices = [100, 80, 60, 70, 60, 75, 85];
// Create an empty stack array
// Create a span array filled with zeros
# Your code here

Hint

Use const stack: number[] = []; and const span: number[] = new Array(prices.length).fill(0);

3

Calculate the stock span using a stack

Use a for loop with variable i from 0 to prices.length - 1. Inside the loop, use a while loop to pop from stack while stack is not empty and prices[stack[stack.length - 1]] <= prices[i]. Then calculate span[i] as i + 1 if stack is empty, otherwise as i - stack[stack.length - 1]. Finally, push i onto stack.

DSA Typescript

const prices = [100, 80, 60, 70, 60, 75, 85];
const stack: number[] = [];
const span: number[] = new Array(prices.length).fill(0);
// Calculate span for each day
# Your code here

Hint

Use a for loop and inside it a while loop to pop smaller or equal prices. Calculate span using the stack's top index.

4

Print the stock span array

Print the span array using console.log(span)

DSA Typescript

const prices = [100, 80, 60, 70, 60, 75, 85];
const stack: number[] = [];
const span: number[] = new Array(prices.length).fill(0);

for (let i = 0; i  0 && prices[stack[stack.length - 1]] <= prices[i]) {
        stack.pop();
    }
    span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
    stack.push(i);
}
// Print the span array
# Your code here

Hint

Use console.log(span) to print the final span array.

Practice

1. What does the Stock Span Problem calculate for each day in a list of stock prices?

easy

A. The average stock price over all days

B. The maximum stock price in the entire list

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

D. The difference between the highest and lowest stock price

Solution

1. Step 1: Understand the problem definition

   The Stock Span Problem finds how many days in a row before today had prices less than or equal to today's price.

2. Step 2: Identify what is calculated for each day

   For each day, it counts consecutive previous days with prices not higher than current day.

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 C

4. Quick Check:

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

Hint: Span counts days with price ≤ today's price backward [OK]

Common Mistakes:

• Thinking it finds max price overall
• Confusing span with price difference
• Calculating average price instead

2. Which TypeScript data structure is best suited to efficiently solve the Stock Span Problem?

easy

A. Stack

B. Array

C. Queue

D. Set

Solution

1. Step 1: Recall the problem needs to track previous prices efficiently

   We need to quickly find previous days with prices less or equal to current day.

2. Step 2: Identify the data structure that supports last-in-first-out access

   A stack allows pushing and popping previous prices to compare efficiently.

3. Final Answer:

   Stack -> Option A

4. Quick Check:

   Stack is used for last-in-first-out access [OK]

Hint: Use stack to track previous prices for quick comparison [OK]

Common Mistakes:

• Using queue which is FIFO, not suitable
• Using set which does not maintain order
• Using array without stack logic

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

medium

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

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

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

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 (days 2 and 3)
   Day 4: 60 ≤ 70 -> span 1
   Day 5: 75 > 60, 70 -> span 4 (days 2,3,4,5)
   Day 6: 85 > 75, 70, 80 -> span 6 (days 1 to 6)

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: Count consecutive previous days with price ≤ current day [OK]

Common Mistakes:

• Counting all previous days regardless of price
• Confusing span with cumulative sum
• Miscounting days when price increases

4. Identify the error in this TypeScript snippet for Stock Span calculation:

function calculateSpan(prices: number[]): number[] {
  const stack: number[] = [];
  const span: number[] = [];
  for (let i = 0; i < prices.length; i++) {
    while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
      stack.pop();
    }
    span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
    stack.push(i);
  }
  return span;
}

medium

A. The stack should store prices, not indices

B. The comparison operator should be <= instead of < in while condition

C. The span array is not initialized with zeros

D. The loop should start from i = 1, not 0

Solution

1. Step 1: Analyze the while loop condition

   The condition uses < to pop smaller prices, but equal prices should also be popped to count span correctly.

2. Step 2: Correct the comparison operator

   Change < to <= so that prices equal to current price are popped, ensuring correct span calculation.

3. Final Answer:

   The comparison operator should be <= instead of < in while condition -> Option B

4. Quick Check:

   Use <= to include equal prices in span [OK]

Hint: Use <= in while to pop equal or smaller prices [OK]

Common Mistakes:

• Using < misses equal prices in span
• Storing prices instead of indices in stack
• Starting loop from 1 misses first day

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

hard

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

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

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

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

Solution

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

   Along with span, store index from stack top before popping. If stack empty, store -1.

2. Step 2: Calculate last higher price indices for each day

   Day 0 (10): no previous higher -> -1
   Day 1 (4): previous higher 10 at index 0 -> 0
   Day 2 (5): previous higher 10 at index 0 -> 0
   Day 3 (90): no previous higher -> -1
   Day 4 (120): no previous higher -> -1
   Day 5 (80): previous higher 120 at index 4 -> 4

3. Final Answer:

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

4. Quick Check:

   Last higher price indices match calculated values [OK]

Hint: Store stack top index before popping for last higher price [OK]

Common Mistakes:

• Returning span instead of last higher price indices
• Using price values instead of indices
• Assigning wrong indices when stack is empty