Stock Span Problem Using Stack in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Stock Span Problem?

It is a problem where for each day, you find how many consecutive days before it had a stock price less than or equal to the current day's price.

beginner

Why do we use a stack to solve the Stock Span Problem?

A stack helps keep track of previous days with higher stock prices efficiently, so we can quickly find the span without checking all previous days repeatedly.

intermediate

What does each element in the stack represent in the Stock Span Problem?

Each element in the stack stores the index of a day with a stock price greater than the current day's price.

intermediate

How do you calculate the span for the current day using the stack?

Span = current day index - index of the last higher price day on the stack. If stack is empty, span = current day index + 1.

intermediate

What is the time complexity of the Stock Span Problem solution using a stack?

The time complexity is O(n) because each element is pushed and popped at most once.

What does the stack store in the Stock Span Problem?

A Indices of days with higher stock prices

B Stock prices themselves

C Span values

D Indices of days with lower stock prices

The stack stores indices of days with higher stock prices to help calculate spans efficiently.

If the stack is empty when calculating span for day i, what is the span?

A i + 1

B 0

C 1

D i

If no previous higher price day exists, span is all days up to current, which is i + 1.

What is the main advantage of using a stack for the Stock Span Problem?

A Avoids using arrays

B Uses less memory

C Simplifies code but slower

D Reduces time complexity to O(n)

Using a stack reduces the time complexity from O(n^2) to O(n).

What happens to stack elements when a new day's price is higher than the top of the stack?

A Clear the stack

B Push new price without popping

C Pop elements until top is higher

D Ignore the new price

We pop elements with lower or equal prices to find the last higher price day.

What does the span value represent for a day?

A Number of days with higher price

B Number of consecutive days before with price less or equal

C Total days in the data

D Price difference from previous day

Span counts consecutive previous days with stock price less than or equal to current day.

Explain how a stack helps solve the Stock Span Problem efficiently.

Think about how the stack keeps track of previous higher prices.

Describe the step-by-step process to calculate the span for each day using a stack.

Imagine walking through days and comparing prices using the stack.

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