Introduction

The Stock Span Problem involves finding the span of stock prices for each day.

The span of a stock’s price today is:

Number of consecutive days before todaywhere price was less than or equal to today's price

The task is to:

  • calculate span for every day

This problem is one of the most important applications of:

Monotonic Stack

This problem helps in understanding:

  • stack optimization
  • previous greater element
  • span calculation
  • efficient traversal

Example

Input:prices =
[100,80,60,70,60,75,85]

Output:
[1,1,1,2,1,4,6]

Explanation:
100 → span 1
80 → span 1

70 → spans:
60,70

85 → spans:
80,60,70,60,75,85

Constraints

1 <= prices.length <= 10^51 <= prices[i] <= 10^5

Approach 1 : Brute Force Traversal

Explanation

The simplest way is:

  1. Traverse each day
  2. Search previous days
  3. Count consecutive smaller prices

This works but repeated searching becomes inefficient.

Steps

  1. Traverse prices.
  2. Move left side.
  3. Count valid consecutive days.
  4. Store span.
  5. Return result array.

Dry Run

Input:[100,80,60,70]

100:
Span = 1

80:
No previous smaller chain
Span = 1

70:
60 <= 70
Span = 2

Result:
[1,1,1,2]

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)
Explanation:
Previous days are repeatedly searched.

Space Complexity: O(1)
Explanation:
Only output array is used.

Approach 2 : Monotonic Stack

Explanation

The optimized solution uses:

 Monotonic Decreasing Stack

Idea:

  • stack stores indices
    of greater stock prices
  • remove smaller prices
    while traversing

Process:

  1. Traverse prices
  2. Remove smaller/equal prices
  3. Remaining top:
    • previous greater element
  4. Calculate span

This avoids repeated searching.

Steps

  1. Create stack.
  2. Traverse prices.
  3. Remove smaller prices.
  4. Calculate span.
  5. Push current index.

Dry Run

Input:[100,80,60,70]

Stack:
[]

100:
Span = 1
Push index 0

80:
Previous greater:
100
Span = 1

70:
Remove 60
Previous greater:
80
Span = 2

Result:
[1,1,1,2]

Monotonic Stack Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each index is pushed and popped once.

Space Complexity: O(n)
Explanation:
Stack stores indices.

Edge Cases

  1. Strictly increasing prices
  2. Strictly decreasing prices
  3. Equal prices
  4. Single day
  5. Large input size

Why This Problem is Important

Stock Span Problem helps in understanding:

  1. Monotonic stacks
  2. Previous greater element
  3. Efficient span calculation
  4. Stack optimization
  5. Linear traversal

It is one of the most important monotonic stack interview problems.

Real-World Applications

Stock span concepts are used in:

  1. Financial analysis
  2. Trading systems
  3. Market trend analysis
  4. Performance monitoring
  5. Historical pattern tracking

Common Mistakes

  1. Incorrect stack condition
  2. Forgetting equal values
  3. Wrong span calculation
  4. Using values instead of indices

Interview Tips

Interviewers often expect:

  1. Monotonic stack explanation
  2. Previous greater reasoning
  3. Span calculation understanding

Always explain:

  • why indices are stored
  • how previous greater element helps
  • why each index is processed once

Related Questions

  1. Next Greater Element
  2. Daily Temperatures
  3. Largest Rectangle in Histogram
  4. Trapping Rain Water
  5. Online Stock Span

Final Takeaway

The Stock Span Problem is a fundamental monotonic stack problem that teaches efficient span calculation and previous-greater optimization techniques. Understanding this problem builds a strong foundation for advanced stack and linear traversal interview problems.