Stock Span Problem Using Stack in DSA Java - 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, a special list where you add and remove items only from the top, to solve this efficiently. This helps us quickly find the answer for each day without checking all previous days one by one. It is useful in finance to analyze stock trends.

Why it matters

Without this method, checking stock prices for many days would take a long time, especially with lots of data. The stack approach speeds this up, saving time and computing power. This means traders and analysts can get quick insights and make better decisions. Without it, analyzing stock trends would be slow and less practical.

Where it fits

Before learning this, you should understand basic arrays and stacks. After this, you can explore other stack problems like Next Greater Element or learn about more complex data structures like queues and trees.

Mental Model

Core Idea

Use a stack to keep track of days with higher stock prices to quickly find how far back the current price is greater or equal.

Think of it like...

Imagine a line of people waiting to buy tickets, where each person can only see the people in front of them who are shorter or equal in height. The stack helps remember those taller people blocking the view, so you know how many people behind are shorter or equal.

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

Build-Up - 6 Steps

1

Foundation

Understanding Stock Span Problem

Concept: Learn what the stock span means and the problem statement.

The stock span for a day is the count of consecutive days before it where the stock price was less than or equal to the price on that day. For example, if prices are [100, 80, 60, 70, 60, 75, 85], the span for day 6 (price 75) is 4 because prices on days 3, 4, 5, and 6 are less or equal to 75.

Result

You understand the problem: for each day, find how many previous days had prices less or equal to today's price.

Understanding the problem clearly is essential before trying to solve it efficiently.

2

Foundation

Basics of Stack Data Structure

Concept: Learn what a stack is and how it works (LIFO).

A stack is like a pile of plates: you add (push) plates on top and remove (pop) from the top only. It helps keep track of items in order and is useful when you need to remember recent items and remove them in reverse order.

Result

You can use a stack to store and retrieve data in a last-in-first-out way.

Knowing how stacks work is key to solving the stock span problem efficiently.

3

Intermediate

Naive Approach to Stock Span

🤔Before reading on: do you think checking all previous days for each day is efficient or slow? Commit to your answer.

Concept: The simple way is to check each previous day until you find a higher price.

For each day, start from the previous day and move backward until you find a day with a price higher than today's. Count how many days you passed. This works but takes a lot of time for many days.

Result

The time taken is O(n^2) for n days, which is slow for large data.

Understanding the naive method shows why we need a better, faster approach.

4

Intermediate

Using Stack to Optimize Span Calculation

🤔Before reading on: do you think a stack can help avoid checking all previous days? Commit to yes or no.

Concept: Use a stack to keep indexes of days with prices higher than the current day to skip unnecessary checks.

We push the index of the first day onto the stack. For each new day, pop from the stack while the price at the top index is less or equal to current price. The span is current day index minus the top of the stack after popping, or current day index + 1 if stack is empty. Then push current day index.

Result

This reduces time complexity to O(n) because each day is pushed and popped at most once.

Using a stack cleverly skips repeated comparisons, making the solution efficient.

5

Advanced

Java Implementation of Stock Span Using Stack

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

Concept: Implement the stack-based solution in Java using indexes for efficient access.

import java.util.Stack; public class StockSpan { public static int[] calculateSpan(int[] prices) { int n = prices.length; int[] span = new int[n]; Stack stack = new Stack<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) { stack.pop(); } span[i] = stack.isEmpty() ? (i + 1) : (i - stack.peek()); 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 + " "); } } }

Result

Output: 1 1 1 2 1 4 6

Using indexes in the stack allows quick calculation of spans without storing prices directly.

6

Expert

Why Stack Approach is O(n) Time Complexity

🤔Before reading on: do you think each element can be pushed and popped multiple times? Commit to your answer.

Concept: Each element is pushed and popped at most once, making the total operations linear.

When iterating, each price index is pushed once onto the stack. It can be popped only when a higher price comes. Since no index is pushed again after popping, total push and pop operations are at most 2n. This guarantees O(n) time complexity.

Result

The algorithm runs efficiently even for large input sizes.

Understanding the push-pop limit explains why the stack method is optimal.

Under the Hood

The stack stores indexes of days with strictly higher prices. When a new price comes, it removes all days with lower or equal prices from the stack, ensuring the top always points to the last day with a higher price. This allows direct calculation of the span by subtracting indexes.

Why designed this way?

This design avoids repeated backward scanning by remembering only relevant days. Alternatives like checking all previous days are slow. The stack approach balances memory and speed efficiently.

Prices: 100  80  60  70  60  75  85
Index:   0   1   2   3   4   5   6
Stack:  ┌─────┐
        │ 0   │ <- index of 100
        └─────┘
Push 1: price 80 <= 100, stack top stays 0
Push 2: price 60 <= 80, stack top stays 0
Push 3: price 70 > 60, pop 2
        price 70 <= 80, stack top 1
Push 4: price 60 <= 70, stack top 3
Push 5: price 75 > 60, pop 4
        price 75 > 70, pop 3
        price 75 <= 80, stack top 1
Push 6: price 85 > 75, pop 5
        price 85 > 80, pop 1
        price 85 <= 100, stack top 0

Myth Busters - 3 Common Misconceptions

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

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

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

Why it matters: Storing prices instead of indexes makes it hard to calculate spans and slows down the algorithm.

Quick: Is the time complexity of the stack solution O(n^2) or O(n)? Commit to your answer.

Common Belief: Because of the while loop inside the for loop, the time complexity is O(n^2).

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

Why it matters: Misunderstanding complexity can lead to rejecting an efficient solution as slow.

Quick: Does the span count only strictly lower prices or also equal prices? Commit to your answer.

Common Belief: Span counts only days with strictly lower prices than today.

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

Why it matters: Counting only strictly lower prices gives wrong span results and misrepresents trends.

Expert Zone

1

The stack approach can be adapted to find spans for other comparison conditions by changing the comparison operator.

2

Using indexes instead of prices in the stack reduces memory usage and simplifies span calculation.

3

The algorithm's linear time depends on the monotonic property of the stack, which is a subtle but powerful invariant.

When NOT to use

If you need spans for non-consecutive days or complex conditions like multiple stocks simultaneously, this approach is limited. Alternatives include segment trees or binary indexed trees for range queries.

Production Patterns

Used in financial software for real-time stock analysis, this pattern helps quickly update spans as new prices arrive. It also appears in competitive programming as a classic stack problem.

Connections

Next Greater Element Problem

Both use stacks to find the next higher value efficiently.

Understanding one helps solve the other since they share the same stack-based pattern.

Monotonic Stack Pattern

Stock span is a classic example of monotonic stack usage where stack elements maintain a sorted order.

Recognizing monotonic stacks helps solve many range and comparison problems efficiently.

Real-Life Queue Management

Stack usage in stock span is like managing a line where only certain people remain visible based on height or priority.

This connection shows how data structures model real-world ordering and visibility problems.

Common Pitfalls

#1 Using prices instead of indexes in the stack.

Wrong approach:

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

Correct approach:

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

Root cause:

Confusing what the stack stores leads to wrong comparisons and logic errors.

#2 Calculating span as stack size instead of index difference.

Wrong approach:

span[i] = stack.size();

Correct approach:

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

Root cause:

Misunderstanding how span relates to positions rather than count of elements.

#3 Not handling empty stack case before accessing top element.

Wrong approach:

span[i] = i - stack.peek(); // without checking if stack is empty

Correct approach:

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

Root cause:

Ignoring empty stack leads to runtime errors and crashes.

Key Takeaways

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

A stack stores indexes of days with higher prices to quickly calculate spans without checking all previous days.

Each price index is pushed and popped at most once, making the algorithm run in linear time.

Using indexes in the stack allows direct calculation of spans by subtracting positions.

Understanding the monotonic stack pattern unlocks efficient solutions to many 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 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