Stock Span Problem Using Stack in DSA Typescript - Deep Dive

Overview - Stock Span Problem Using Stack

What is it?

The Stock Span Problem is about finding how many consecutive days before today the stock price was less than or equal to today's price. We use a stack to efficiently track these days and calculate the span for each day. This helps us understand the stock's performance trend over time.

Why it matters

Without this problem's solution, calculating the span for each day would take a lot of time, especially for many days, making it slow and inefficient. Using a stack speeds up the process, saving time and resources, which is important for real-time stock analysis and decision-making.

Where it fits

Before learning this, you should understand basic arrays and stacks. After this, you can explore other stack-based problems like Next Greater Element or advanced data structures for financial data analysis.

Mental Model

Core Idea

Use a stack to remember days with higher stock prices to quickly find how far back prices were lower or equal.

Think of it like...

Imagine a line of people waiting to buy tickets, where each person only cares about how many people before them have a lower or equal height. The stack helps keep track of these taller people to quickly count the shorter ones behind.

Day:    1   2   3   4   5   6   7
Price:  100 80  60  70  60  75  85
Span:   1   1   1   2   1   4   6

Stack stores indices of days with prices higher than current day to calculate spans.

Build-Up - 6 Steps

1

Foundation

Understanding Stock Span Problem

Concept: What the stock span means and how to calculate it manually.

The stock span for a day is the count of consecutive days before it where the price was less or equal. For example, if prices are [100, 80, 60, 70], the span for day 4 (price 70) is 2 because day 3 (60) is less and day 2 (80) is higher, so we stop counting there.

Result

Manual calculation shows spans: [1, 1, 1, 2]

Understanding the problem manually helps see why a simple loop might be slow for many days.

2

Foundation

Basics of Stack Data Structure

Concept: How a stack works and why it's useful for tracking previous days.

A stack is like a pile of plates: you add (push) on top and remove (pop) from the top. It helps keep track of previous days' prices in order, so we can quickly find the last day with a higher price.

Result

Stack operations allow quick access to recent days with higher prices.

Knowing stack behavior is key to efficiently solving the stock span problem.

3

Intermediate

Using Stack to Calculate Spans

🤔Before reading on: do you think we push all days onto the stack or only some? Commit to your answer.

Concept: We only keep days with prices higher than the current day on the stack to find spans quickly.

For each day, pop days from the stack while their prices are less or equal to current day's price. The span is current day index minus the index on top of the stack after popping, or current day index + 1 if stack is empty. Then push current day index onto stack.

Result

Stack helps calculate spans in O(n) time instead of O(n^2).

Knowing when to pop from the stack avoids unnecessary comparisons and speeds up the solution.

4

Intermediate

Implementing Stock Span in TypeScript

🤔Before reading on: do you think the stack stores prices or indices? Commit to your answer.

Concept: Stack stores indices to calculate spans using positions, not just prices.

function calculateSpan(prices: number[]): number[] { const n = prices.length; const span = new Array(n).fill(1); const stack: number[] = []; for (let i = 0; i < n; 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; } // Example usage: const prices = [100, 80, 60, 70, 60, 75, 85]; console.log(calculateSpan(prices));

Result

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

Storing indices instead of prices allows quick span calculation using positions.

5

Advanced

Time Complexity and Efficiency

🤔Before reading on: do you think the algorithm runs in linear or quadratic time? Commit to your answer.

Concept: The stack-based solution runs in linear time because each element is pushed and popped at most once.

Though there is a nested while loop, each price index is pushed once and popped once, so total operations are proportional to number of days. This makes the solution efficient for large inputs.

Result

Algorithm runs in O(n) time, much faster than naive O(n^2).

Understanding amortized analysis explains why the stack approach is efficient despite nested loops.

6

Expert

Handling Real-Time Stock Data Streams

🤔Before reading on: can this stack approach be adapted for streaming data? Commit to your answer.

Concept: The stack method can be adapted to process stock prices as they arrive in real-time without reprocessing all data.

For streaming data, maintain the stack and spans as new prices come in. Each new price is processed with the same logic, updating the stack and span array dynamically. This allows continuous span calculation without restarting.

Result

Real-time span calculation is possible with incremental updates.

Knowing how to adapt batch algorithms for streaming data is crucial for real-world financial applications.

Under the Hood

The stack stores indices of days with strictly higher prices. When a new price arrives, we pop all indices with prices less or equal to it, effectively skipping days that don't limit the span. The span is the distance between the current day and the last higher price day on the stack. This avoids checking every previous day individually.

Why designed this way?

This design avoids repeated comparisons by remembering only relevant days that affect the span. Alternatives like checking all previous days would be too slow. The stack approach balances simplicity and efficiency, making it suitable for large datasets.

Prices: 100  80  60  70  60  75  85
Index:   0   1   2   3   4   5   6

Stack operations:
Day 0: stack empty -> push 0
Stack: [0]
Day 1: price 80 <= 100 (top) -> push 1
Stack: [0,1]
Day 2: price 60 <= 80 -> push 2
Stack: [0,1,2]
Day 3: price 70 > 60 -> pop 2
price 70 <= 80 -> push 3
Stack: [0,1,3]
Day 4: price 60 <= 70 -> push 4
Stack: [0,1,3,4]
Day 5: price 75 > 60 pop 4
price 75 > 70 pop 3
price 75 <= 80 push 5
Stack: [0,1,5]
Day 6: price 85 > 75 pop 5
price 85 > 80 pop 1
price 85 <= 100 push 6
Stack: [0,6]

Myth Busters - 3 Common Misconceptions

Quick: Does the stack store prices or indices? Commit to your answer.

Common Belief: The stack stores the actual stock prices to compare directly.

Reality: The stack stores indices of days, not prices, to calculate spans using positions.

Why it matters: Storing prices would make it hard to calculate spans because we need day positions to find how many days back the span extends.

Quick: Is the time complexity O(n^2) because of nested loops? Commit to your answer.

Common Belief: Because of the nested while loop inside the for loop, the algorithm runs in quadratic time.

Reality: Each element is pushed and popped at most once, so the total operations are linear, O(n).

Why it matters: Misunderstanding complexity can lead to rejecting an efficient solution and using slower methods.

Quick: Does the span count only days with strictly lower prices? Commit to your answer.

Common Belief: Span counts only days with prices strictly less than today's price.

Reality: Span counts days with prices less than or equal to today's price.

Why it matters: Incorrect span calculation leads to wrong results and misinterpretation of stock trends.

Expert Zone

1

The stack approach can be extended to handle queries for previous greater or smaller elements by adjusting the comparison condition.

2

In real-time systems, maintaining the stack incrementally avoids recomputation and supports live analytics.

3

Amortized analysis explains why the nested loop does not cause quadratic time, a subtlety often missed.

When NOT to use

If you need spans based on complex conditions (like price changes with thresholds or multiple stocks), this simple stack approach is insufficient. Alternatives include segment trees or balanced binary search trees for range queries.

Production Patterns

Used in financial software to quickly compute stock trends, in trading algorithms to detect momentum, and in interview coding tests to demonstrate stack usage and time complexity optimization.

Connections

Next Greater Element Problem

Builds-on and shares the same stack pattern for finding next larger values.

Understanding the stock span problem helps grasp the next greater element problem, as both use stacks to track previous or next higher values efficiently.

Amortized Analysis

Explains the time complexity behavior of the stack operations in this problem.

Knowing amortized analysis clarifies why nested loops here do not mean quadratic time, a key insight for algorithm efficiency.

Queue Management in Real Life

Similar pattern of tracking people waiting and skipping those who don't affect the count.

Recognizing this pattern in everyday queues helps understand how stacks skip irrelevant elements to speed up calculations.

Common Pitfalls

#1 Storing prices in the stack instead of indices.

Wrong approach:

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

Correct approach:

const stack: 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);
}

Root cause:

Confusing the need for indices to calculate spans with the actual price values.

#2 Calculating span as the difference between prices instead of indices.

Wrong approach:

span[i] = prices[i] - prices[stack[stack.length - 1]];

Correct approach:

span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];

Root cause:

Misunderstanding that span counts days, not price differences.

#3 Not popping all smaller or equal prices from the stack.

Wrong approach:

if (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
stack.pop();
}
// Only one pop per iteration

Correct approach:

while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
stack.pop();
}

Root cause:

Failing to remove all irrelevant days leads to incorrect span calculation.

Key Takeaways

The stock span problem measures how many consecutive previous days had prices less or equal to today's price.

Using a stack to store indices of days with higher prices allows efficient span calculation in linear time.

Each price index is pushed and popped at most once, making the algorithm fast even for large data.

Storing indices instead of prices is crucial to calculate spans based on day positions.

This stack pattern is a foundation for many similar problems and can be adapted for real-time data streams.

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