Stock Span Problem Using Stack in DSA Javascript - Execution Trace

Concept Flow - Stock Span Problem Using Stack

Start with empty stack

↓

For each day's price

↓

While stack not empty and top price <= current price

↓

Pop stack

↓

Calculate span: current index - top of stack index

↓

Push current day index onto stack

↓

Repeat for next day

↓

End: return span array

We use a stack to keep indexes of days with higher prices. For each day, pop lower prices, calculate span, then push current day.

Execution Sample

DSA Javascript

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

Calculates the stock span for each day using a stack to track previous higher prices.

Execution Table

Step	Operation	Current Day (i)	Price	Stack (indexes)	Span Array	Visual State
1	Start	-	-	[]	[]	Stack empty, span empty
2	Process day 0	0	100	[]	[1]	Stack empty, span[0] = 0+1=1, push 0
3	Process day 1	1	80	[0]	[1, 1]	Top price 100 > 80, no pop, span[1] = 1-0=1, push 1
4	Process day 2	2	60	[0,1]	[1,1,1]	Top price 80 > 60, no pop, span[2] = 2-1=1, push 2
5	Process day 3	3	70	[0,1,2]	[1,1,1,2]	Pop 2 (60 <= 70), top now 1(80) > 70 no pop, span[3] = 3-1=2, push 3
6	Process day 4	4	60	[0,1,3]	[1,1,1,2,1]	Top price 70 > 60 no pop, span[4] = 4-3=1, push 4
7	Process day 5	5	75	[0,1,3,4]	[1,1,1,2,1,4]	Pop 4 (60 <= 75), pop 3 (70 <= 75), top now 1(80) > 75 no pop, span[5] = 5-1=4, push 5
8	Process day 6	6	85	[0,1,5]	[1,1,1,2,1,4,5]	Pop 5 (75 <= 85), pop 1 (80 <= 85), top now 0(100) > 85 no pop, span[6] = 6-0=6, push 6
9	End	-	-	[0,6]	[1,1,1,2,1,4,6]	All days processed, final span array returned

💡 All days processed, loop ends after day 6

Variable Tracker

Variable	Start	After Day 0	After Day 1	After Day 2	After Day 3	After Day 4	After Day 5	After Day 6	Final
stack	[]	[0]	[0,1]	[0,1,2]	[0,1,3]	[0,1,3,4]	[0,1,5]	[0,6]	[0,6]
span	[]	[1]	[1,1]	[1,1,1]	[1,1,1,2]	[1,1,1,2,1]	[1,1,1,2,1,4]	[1,1,1,2,1,4,6]	[1,1,1,2,1,4,6]
i	-	0	1	2	3	4	5	6	-
prices[i]	-	100	80	60	70	60	75	85	-

Key Moments - 3 Insights

Why do we pop from the stack while the top price is less or equal to current price?

Because those days have prices not greater than current, so their span is included in current day's span. See execution_table rows 5,7,8 where popping happens before calculating span.

Why do we calculate span as i - stack top index when stack is not empty?

Because the top of stack is the last day with price greater than current, so span is days between them. See execution_table row 3 where span[1] = 1 - 0 = 1.

What happens when stack is empty before pushing current day?

It means no previous higher price day exists, so span is i + 1 (all days so far). See execution_table row 2 where stack empty leads to span[0] = 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the stack state after popping?

A [0,1]

B [0,1,3]

C [0,1,2]

D [0]

💡 Hint

Check the 'Stack (indexes)' column at step 5 after popping 2

At which step does the span for day 5 get calculated as 4?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at 'Span Array' column and 'Current Day (i)' at step 7

If the price on day 6 was 50 instead of 85, what would happen to the stack at step 8?

A Stack would pop multiple elements

B Stack would remain unchanged

C Stack would only push day 6 index without popping

D Stack would become empty

💡 Hint

Compare price 50 with top stack price 75 at step 8 in execution_table

Concept Snapshot

Stock Span Problem Using Stack:
- Use stack to store indexes of days with higher prices
- For each day, pop stack while top price <= current price
- Span = current day index - top of stack index (or i+1 if stack empty)
- Push current day index onto stack
- Result: span array showing consecutive days with price <= current day

Full Transcript

The Stock Span Problem calculates how many consecutive days before today had stock prices less or equal to today's price. We use a stack to keep indexes of days with higher prices. For each day, we pop from the stack all days with prices less or equal to current price. Then, if stack is empty, span is current day index plus one; else span is difference between current day and top of stack index. We push current day index onto stack and continue. This process efficiently computes spans in one pass. The execution table shows step-by-step stack changes and span calculations for example prices. Key moments clarify why popping happens and how span is computed. The visual quiz tests understanding of stack state and span values at different steps.

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