Stock Span Problem Using Stack in DSA Java - 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 from stack

↓

Calculate span: if stack empty -> i+1 else i - top index

↓

Push current day index onto stack

↓

Move to next day

↓

Repeat until all days processed

↓

Return span array

We use a stack to keep track of indices of days with higher prices. For each day, we pop days with prices less or equal to current, then calculate span based on stack top.

Execution Sample

DSA Java

int[] prices = {100, 80, 60, 70, 60, 75, 85};
int[] span = new int[prices.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < prices.length; i++) {
  while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
    stack.pop();
  }
  span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
  stack.push(i);
}

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

Execution Table

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

💡 All days processed, loop ends

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	-	-

Key Moments - 3 Insights

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

Because those days have prices not greater than current, so they don't limit the span. We remove them to find the nearest previous day with a higher price (see execution_table rows 5,7,8).

What does it mean when the stack is empty before calculating span?

It means no previous day has a higher price, so the span is the entire length from day 0 to current day (i+1), as shown in execution_table rows 2 and 8.

Why do we store indices in the stack instead of prices?

Indices let us calculate the span by subtracting positions (i - stack.peek()), which is needed to find how many consecutive days the price was less or equal (see span calculation in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the stack content after processing day 3?

A [0,1,2,3]

B [0,1,3]

C [0,3]

D [3]

💡 Hint

Refer to the 'Stack (Indices)' column at step 5 in execution_table.

At which step does the span for day 5 become 4?

A Step 7

B Step 5

C Step 6

D Step 8

💡 Hint

Check the 'Span[i]' column for day 5 in execution_table.

If the price on day 6 was 90 instead of 85, how would the stack change at step 8?

A Stack would remain [0,1,5]

B Stack would pop indices 5,1,0 and push 6 only

C Stack would pop indices 5 and 1 but keep 0 and push 6

D Stack would pop only index 5 and push 6

💡 Hint

Higher price causes more pops until stack empty or top price > current (see execution_table step 8).

Concept Snapshot

Stock Span Problem Using Stack:
- Use a stack to store indices of days with higher prices.
- For each day, pop stack while top price <= current price.
- Span = i+1 if stack empty else i - stack.peek().
- Push current day index onto stack.
- Time complexity: O(n) due to each element pushed/popped once.

Full Transcript

The Stock Span Problem calculates how many consecutive days before the current day had prices less or equal to today's price. We use a stack to keep indices of days with higher prices. For each day, we pop from the stack all days with prices less or equal to current. If the stack is empty, the span is the whole range from day 0 to current day. Otherwise, span is the difference between current day and the top index on the stack. We then push the current day index onto the stack. This approach efficiently computes spans in linear time.

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 and including 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 difference between the highest and lowest stock price

D. The total sum of stock prices up to the current day

Solution

1. Step 1: Understand the problem definition

   The Stock Span Problem finds, for each day, how many consecutive days before and including the current day had stock prices less than or equal to the current day's price.

2. Step 2: Clarify what is being counted

   It counts days backward until a higher price is found or the start is reached.

3. Final Answer:

   The number of consecutive days before and including the current day with a price less than or equal to the current day's price -> Option A

4. Quick Check:

   Span counts consecutive lower/equal prices [OK]

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

Common Mistakes:

• Confusing span with maximum price
• Counting all previous days instead of consecutive ones
• Calculating price differences instead of counts

2. Which Java data structure is most suitable to efficiently solve the Stock Span Problem?

easy

A. Queue

B. ArrayList

C. HashMap

D. Stack

Solution

1. Step 1: Identify the need for tracking previous prices

   The problem requires checking previous days' prices to find the span efficiently.

2. Step 2: Choose a data structure that supports last-in-first-out access

   A stack allows pushing and popping prices or indices to quickly find the last higher price.

3. Final Answer:

   Stack -> Option D

4. Quick Check:

   Stack supports efficient previous day price checks [OK]

Hint: Use stack to track previous prices efficiently [OK]

Common Mistakes:

• Using ArrayList which is inefficient for this problem
• Choosing HashMap which doesn't maintain order
• Using Queue which is FIFO, not suitable here

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

medium

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

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

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

D. [1, 1, 1, 1, 1, 1, 1]

Solution

1. Step 1: Calculate span for each day

   Day 0: 100, no previous higher price, span=1
   Day 1: 80 ≤ 100? Yes, but previous higher price is 100, so span=1
   Day 2: 60 ≤ 80? Yes, but previous higher price is 80, so span=1
   Day 3: 70 > 60, span=2 (days 2 and 3)
   Day 4: 60 ≤ 70? Yes, but previous higher price is 70, so span=1
   Day 5: 75 > 60 and 70, span=4 (days 2,3,4,5)
   Day 6: 85 > 75, 70, 60, span=6 (days 1 to 6)

2. Step 2: Confirm final span array

   The span array is [1, 1, 1, 2, 1, 4, 6].

3. Final Answer:

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

4. Quick Check:

   Span matches consecutive lower/equal days [OK]

Hint: Count consecutive days with price ≤ current day [OK]

Common Mistakes:

• Counting all previous days instead of consecutive
• Misapplying stack logic causing wrong spans
• Confusing span with price values

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

for (int i = 0; i < prices.length; i++) {
  while (!stack.isEmpty() && prices[stack.peek()] < prices[i]) {
    stack.pop();
  }
  span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
  stack.push(i);
}

medium

A. The stack should store prices, not indices

B. The span calculation should use i + stack.peek() instead of i - stack.peek()

C. The comparison operator should be <= instead of <

D. The loop should start from i = 1 instead of 0

Solution

1. Step 1: Analyze the while condition for popping stack

   The condition uses < to pop indices with prices less than current price, but it should pop prices less than or equal to current price to correctly count span.

2. Step 2: Confirm correct comparison operator

   Using <= ensures all previous days with price ≤ current are popped, giving correct span.

3. Final Answer:

   The comparison operator should be <= instead of < -> Option C

4. Quick Check:

   Use <= to pop all lower or equal prices [OK]

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

Common Mistakes:

• Using < instead of <= causing wrong spans
• Storing prices instead of indices in stack
• Starting loop at wrong index

5. Given stock prices [10, 4, 5, 90, 120, 80], what is the span array if the stack is implemented to store prices instead of indices?

hard

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

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

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

D. [1, 1, 2, 1, 2, 1]

Solution

1. Step 1: Understand stack storing prices instead of indices

   Without indices, we cannot calculate span as difference of indices; span calculation fails.

2. Step 2: Resulting span values

   Each day is treated as isolated, so span defaults to 1 for all days.

3. Final Answer:

   [1, 1, 1, 1, 1, 1] -> Option B

4. Quick Check:

   Stack must store indices for correct span [OK]

Hint: Stack must store indices, not prices, for correct span [OK]

Common Mistakes:

• Storing prices causes incorrect span calculation
• Assuming span grows without index info
• Ignoring index difference in span formula