Stock Span Problem Using Stack in DSA Javascript - 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. This helps us quickly calculate the span for each day without checking all previous days one by one.

Why it matters

Without this method, calculating stock spans would be slow and inefficient, especially for large data. Using a stack speeds up the process, saving time and computing power. This is important in real-world finance where quick decisions based on stock trends matter.

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 Histogram Area. This problem builds your skill in using stacks for range queries.

Mental Model

Core Idea

Use a stack to remember days with higher stock prices so you can 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 shorter or equal height. The stack helps keep track of these taller people so you don't have to look back at everyone.

Day:    1    2    3    4    5
Price:  100  80   60   70   60
Stack:  [1]
Span:   1    1    1    2    1

Day:    6    7
Price:  75   85
Stack:  [1,4]
Span:   4    6

Explanation:
- Stack stores indices of days with prices higher than current day.
- Span counts how many days back prices were <= current price.

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 with prices less or equal to that day's price. For example, if prices are [100, 80, 60, 70, 60, 75, 85], the span for day 4 (price 70) is 2 because day 3 (60) is less than 70, but day 2 (80) is not.

Result

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

Understanding the problem manually helps you see why checking all previous days one by one is slow and motivates a better method.

2

Foundation

Basics of Stack Data Structure

Concept: How a stack works and why it helps in problems like this.

A stack is like a pile of plates: you add (push) on top and remove (pop) from the top only. It helps keep track of recent items in order. For the stock span, we use a stack to remember days with higher prices so we can skip checking many days.

Result

Stack operations: push, pop, peek (top element) work in constant time.

Knowing stack basics is key because it allows efficient look-back without scanning all previous days.

3

Intermediate

Using Stack to Track Previous Higher Prices

🤔Before reading on: do you think we should store prices or indices in the stack? Commit to your answer.

Concept: Store indices of days with higher prices to calculate spans efficiently.

We push the index of the current day onto the stack after popping all days with prices less or equal to current price. This way, the top of the stack always points to the last day with a higher price. The span is current day index minus top of stack index.

Result

For day 6 (price 75), stack top is day 2 (price 80), so span = 6 - 2 = 4.

Storing indices instead of prices lets us calculate spans by simple subtraction, making the solution efficient.

4

Intermediate

Implementing Stock Span Algorithm in JavaScript

🤔Before reading on: do you think the algorithm runs in O(n) or O(n^2) time? Commit to your answer.

Concept: Use a single pass with stack operations to compute spans in linear time.

We loop through prices array. For each price, pop from stack while top price <= current price. If stack empty, span is current index + 1. Else span is current index - top of stack index. Push current index to stack. This avoids nested loops.

Result

Output spans for prices [100, 80, 60, 70, 60, 75, 85] is [1, 1, 1, 2, 1, 4, 6]

This step shows how stack reduces time complexity from quadratic to linear, a huge efficiency gain.

5

Advanced

Handling Edge Cases and Large Inputs

🤔Before reading on: do you think the stack can grow as large as the input size? Commit to your answer.

Concept: Understand stack size limits and behavior with equal prices or strictly increasing sequences.

If prices are strictly decreasing, stack grows to size n because no elements get popped. If prices are equal, popping happens for equal or smaller prices. The algorithm handles these cases gracefully without extra code.

Result

Stack size varies but never exceeds input size; algorithm remains O(n).

Knowing stack behavior in edge cases helps prevent bugs and ensures robustness in production.

6

Expert

Optimizing Memory and Understanding Amortized Analysis

🤔Before reading on: do you think each element is pushed and popped multiple times or just once? Commit to your answer.

Concept: Each element is pushed and popped at most once, making the algorithm efficient in practice.

Though popping happens inside a loop, each element is pushed once and popped once. This means total stack operations are at most 2n, so time complexity is O(n) amortized. Memory usage is minimal and predictable.

Result

Algorithm runs efficiently even for very large inputs without hidden costs.

Understanding amortized analysis explains why the algorithm is fast despite nested loops in code.

Under the Hood

The stack stores indices of days with strictly higher prices. When a new price arrives, the algorithm pops all indices with prices less or equal to current price, ensuring the top of the stack always points to the last day with a higher price. This allows calculating the span by subtracting indices. Each element is pushed once and popped once, making the process efficient.

Why designed this way?

The problem requires checking previous days quickly. A naive approach checks all previous days, which is slow. Using a stack to remember only relevant days reduces redundant checks. This design balances simplicity and efficiency, avoiding complex data structures.

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

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

Span calculation:
Span[i] = i - stack_top if stack not empty else i + 1

Myth Busters - 4 Common Misconceptions

Quick: Do you think the stack stores prices directly or indices? Commit to your answer.

Common Belief: The stack stores the actual stock prices to compare with the current price.

Reality: The stack stores indices of days, not prices, to calculate spans by index subtraction.

Why it matters: Storing prices would make it hard to calculate spans efficiently and complicate the logic.

Quick: Do you think the algorithm runs in quadratic time because of nested loops? Commit to your answer.

Common Belief: Because there is a loop inside a loop (while inside for), the algorithm is O(n^2).

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

Why it matters: Misunderstanding complexity can lead to rejecting this efficient solution for large inputs.

Quick: Do you think equal prices are treated the same as smaller prices in popping? Commit to your answer.

Common Belief: Equal prices are not popped from the stack because they are not smaller.

Reality: Equal prices are popped to maintain correct span calculation.

Why it matters: Ignoring equal prices causes incorrect spans and bugs in real data.

Quick: Do you think the stack can grow indefinitely without popping? Commit to your answer.

Common Belief: The stack can grow as large as the number of days without popping.

Reality: Stack size varies but elements get popped when a higher price appears, preventing unbounded growth.

Why it matters: Assuming unbounded stack growth leads to wrong memory usage expectations and inefficient designs.

Expert Zone

1

The algorithm's amortized O(n) time comes from each element being pushed and popped once, a subtle but powerful efficiency.

2

Handling equal prices by popping them ensures spans count consecutive days correctly, which is often overlooked.

3

Stack indices allow direct span calculation by subtraction, avoiding extra storage or complex data structures.

When NOT to use

This stack-based approach is not suitable if you need spans for non-consecutive days or complex queries like maximum spans over intervals. For such cases, segment trees or binary indexed trees are better alternatives.

Production Patterns

In real trading systems, this algorithm is used to quickly analyze price trends and volumes. It is often combined with sliding window techniques and real-time data streams to provide instant insights.

Connections

Next Greater Element

Builds-on and similar pattern

Both problems use stacks to find the next or previous element greater than the current one, showing a common stack usage pattern.

Amortized Analysis

Underlying efficiency principle

Understanding how each element is pushed and popped once explains why the algorithm is efficient despite nested loops.

Human Queue Management

Real-world process analogy

Managing a queue of people by height or priority is similar to managing a stack of days by price, showing how data structures model real-life ordering.

Common Pitfalls

#1 Storing prices in the stack instead of indices.

Wrong approach:

stack.push(prices[i]); // pushing price values

Correct approach:

stack.push(i); // pushing indices

Root cause:

Confusing what information is needed to calculate spans efficiently.

#2 Not popping equal prices from the stack.

Wrong approach:

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

Correct approach:

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

Root cause:

Misunderstanding that equal prices affect span calculation.

#3 Calculating span as stack top index instead of difference.

Wrong approach:

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

Correct approach:

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

Root cause:

Not realizing span depends on distance between current day and last higher price day.

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 is pushed and popped at most once, making the algorithm run in O(n) time despite nested loops.

Handling equal prices correctly by popping them ensures accurate span counts.

This problem is a classic example of using stacks to solve range queries efficiently and is foundational for similar problems.

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 minimum stock price in the entire list

D. The difference between the current day's price and the previous day's price

Solution

1. Step 1: Understand the problem definition

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

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

   For each day, it counts days backward until a higher price is found or start is reached.

3. Final Answer:

   The number of consecutive days with price less or equal to current day -> Option A

4. Quick Check:

   Span counts consecutive lower/equal prices before today [OK]

Hint: Span counts days with prices ≤ current day price [OK]

Common Mistakes:

• Confusing span with max or min price
• Thinking span is price difference
• Ignoring consecutive days condition

2. Which of the following JavaScript code snippets correctly initializes an empty stack for solving the Stock Span Problem?

easy

A. const stack = 0;

B. const stack = {};

C. const stack = [];

D. const stack = null;

Solution

1. Step 1: Identify the correct data structure for stack

   In JavaScript, a stack is usually implemented as an array to use push and pop methods.

2. Step 2: Check initialization syntax

   An empty array is initialized with [] which is correct for a stack.

3. Final Answer:

   const stack = []; -> Option C

4. Quick Check:

   Stack uses array [] in JavaScript [OK]

Hint: Use array [] to create stack in JavaScript [OK]

Common Mistakes:

• Using object {} instead of array
• Assigning null or number instead of array
• Forgetting to initialize stack before use

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

medium

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

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 price

   Day 0: 100 -> span=1 (no previous days)
   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, 60 -> span=4 (days 4,3,2,1)
   Day 6: 85 > 75, 70, 60, 80 -> span=6 (days 5,3,2,1,0)

2. Step 2: Write the 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 [OK]

Common Mistakes:

• Counting all previous days instead of consecutive
• Mixing up greater and less conditions
• Incorrectly including days with higher prices

4. Identify the error in the following JavaScript code snippet for the Stock Span Problem:

function calculateSpan(prices) {
  const stack = [];
  const span = [];
  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 span calculation formula is incorrect; it should be i + stack[stack.length - 1]

B. There is no error; the code correctly calculates the stock span

C. The stack should store prices, not indices

D. The comparison operator in while loop should be <= instead of <

Solution

1. Step 1: Analyze the while loop condition

   The loop pops indices while the price at top index is less than or equal to current price, which is correct for span calculation.

2. Step 2: Check span calculation formula

   If stack is empty, span is i+1 (all previous days), else difference between current index and top index in stack, which is correct.

3. Step 3: Verify stack usage

   Stack stores indices, which is standard to access prices array correctly.

4. Final Answer:

   There is no error; the code correctly calculates the stock span -> Option B

5. Quick Check:

   Code matches standard stock span algorithm [OK]

Hint: Stack stores indices; span formula uses index difference [OK]

Common Mistakes:

• Changing < to <= breaks correct span logic
• Storing prices instead of indices causes wrong indexing
• Incorrect span formula leads to wrong results

5. Given the stock prices array [10, 4, 5, 90, 120, 80], how would the Stock Span Problem algorithm change if we want to find the span of days with prices strictly less than the current day's price (not less than or equal)? What is the resulting span array?

hard

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

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

C. [1, 1, 1, 4, 5, 1]

D. [1, 2, 3, 4, 5, 6]

Solution

1. Step 1: Understand the strict less than condition

   Change the comparison in the algorithm from ≤ to <, so only days with price strictly less count towards span.

2. Step 2: Calculate spans with strict less than

   Day 0: 10 -> span=1
   Day 1: 4 < 10 -> span=1
   Day 2: 5 > 4 -> span=2 (days 1 and 2)
   Day 3: 90 > 5,4,10 -> span=4 (days 0,1,2,3)
   Day 4: 120 > 90 -> span=5 (days 0 to 4)
   Day 5: 80 < 120 -> span=1

3. Final Answer:

   [1, 1, 2, 4, 5, 1] -> Option A

4. Quick Check:

   Strict less than span matches [1,1,2,4,5,1] [OK]

Hint: Use < instead of ≤ in comparison for strict span [OK]

Common Mistakes:

• Not changing comparison operator correctly
• Counting equal prices in span incorrectly
• Miscounting consecutive days with strict condition