Stock Span Problem Using Stack in DSA Java

Mental Model

We want to find how many consecutive days before today had stock prices less or equal to today's price. We use a stack to remember days with higher prices to quickly jump back.

Analogy: Imagine checking how many days in a row you had cooler or equal weather compared to today by looking back only at days that were warmer, skipping the cooler ones quickly.

Prices: [100, 80, 60, 70, 60, 75, 85]
Stack stores indices of days with prices higher than current day to jump back quickly.
Example stack: [0, 3, 5] means days 0, 3, 5 have higher prices.

Initial:
Index: 0  1  2  3  4  5  6
Price:100 80 60 70 60 75 85
Stack: []
Span:  []

Dry Run Walkthrough

Input: Prices: [100, 80, 60, 70, 60, 75, 85]

Goal: Calculate span array where each element shows how many consecutive previous days had price less or equal to current day

Step 1: Start with day 0, stack empty, push index 0

Stack: [0]
Span: [1, _, _, _, _, _, _]

Why: First day always has span 1 because no previous days

Step 2: Day 1 price 80 less than price at stack top day 0 (100), push index 1

Stack: [0, 1]
Span: [1, 1, _, _, _, _, _]

Why: Price lower, so span is 1, push to stack to check future days

Step 3: Day 2 price 60 less than price at stack top day 1 (80), push index 2

Stack: [0, 1, 2]
Span: [1, 1, 1, _, _, _, _]

Why: Price lower, span 1, push index

Step 4: Day 3 price 70 greater than price at stack top day 2 (60), pop 2; still less than day 1 (80), push 3

Stack: [0, 1, 3]
Span: [1, 1, 1, 2, _, _, _]

Why: Pop days with lower price to find last higher price day; span = current index - stack top index

Step 5: Day 4 price 60 less than price at stack top day 3 (70), push 4

Stack: [0, 1, 3, 4]
Span: [1, 1, 1, 2, 1, _, _]

Why: Lower price, span 1, push index

Step 6: Day 5 price 75 greater than day 4 (60), pop 4; greater than day 3 (70), pop 3; less than day 1 (80), push 5

Stack: [0, 1, 5]
Span: [1, 1, 1, 2, 1, 4, _]

Why: Pop lower prices to find last higher price day; span = 5 - 1 = 4

Step 7: Day 6 price 85 greater than day 5 (75), pop 5; greater than day 1 (80), pop 1; less than day 0 (100), push 6

Stack: [0, 6]
Span: [1, 1, 1, 2, 1, 4, 6]

Why: Pop lower prices to find last higher price day; span = 6 - 0 = 6

Result:

Final span array: [1, 1, 1, 2, 1, 4, 6]

Annotated Code

DSA Java

import java.util.Stack;

public class StockSpan {
    public static int[] calculateSpan(int[] prices) {
        int n = prices.length;
        int[] span = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            // Pop indices with prices less or equal to current price
            while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
                stack.pop();
            }
            // If stack empty, span is i+1 else difference with last higher price day
            span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
            // Push current day index
            stack.push(i);
        }
        return span;
    }

    public static void main(String[] args) {
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        int[] span = calculateSpan(prices);
        for (int s : span) {
            System.out.print(s + " ");
        }
        System.out.println();
    }
}

while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) { stack.pop(); }

Pop indices of days with prices less or equal to current day to find last higher price day

span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();

Calculate span as distance from last higher price day or all days if none

stack.push(i);

Push current day index to stack for future comparisons

Output

1 1 1 2 1 4 6 

Complexity Analysis

Time: O(n) because each element is pushed and popped at most once from the stack

Space: O(n) for the stack and span array to store indices and results

vs Alternative: Naive approach is O(n^2) by checking all previous days for each day, stack reduces it to O(n)

Edge Cases

Empty price array

Returns empty span array without error

DSA Java

int n = prices.length;

All prices equal

Span increases by 1 each day because all previous prices are less or equal

DSA Java

while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) { stack.pop(); }

Strictly decreasing prices

Span is always 1 because no previous day has price less or equal

DSA Java

span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();

When to Use This Pattern

When asked to find how many previous consecutive elements satisfy a condition relative to current, use a stack to jump back efficiently.

Common Mistakes

Mistake: Not popping all smaller or equal prices from stack, causing wrong span calculation
Fix: Use a while loop to pop all indices with prices less or equal to current price

Mistake: Calculating span as i - stack.peek() + 1 instead of i - stack.peek()
Fix: Span is difference between current index and last higher price index, no +1 needed

Summary

Calculates how many consecutive previous days had stock prices less or equal to current day using a stack.

Use when you need to find spans or ranges of previous elements satisfying a condition efficiently.

The key is to use a stack to remember indices of days with higher prices to jump back quickly and avoid repeated checks.

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