Stock Span Problem – Monotonic Stack Pattern

Problem Statement

You are given an array arr[] where arr[i] represents the stock price on the i-th day.

For every day, find the stock span.

The span of a stock's price on a given day is defined as the number of consecutive days ending on that day for which the stock price was less than or equal to the current day's price.

In simpler terms, starting from the current day and moving backward, count how many consecutive days have prices less than or equal to today's price.

Example

Input

[100, 80, 90, 120]

Output

[1, 1, 2, 4]

Understanding the Span

Consider:

Prices

[100, 80, 90, 120]

Day 0

Price:

No previous day exists.

Span:

Day 1

Price:

Previous price:

100 > 80

Span:

Day 2

Price:

Previous prices:

80 <= 90
100 > 90

Span:

Day 3

Price:

Previous prices:

90 <= 120
80 <= 120
100 <= 120

Span:

Final Answer

[1,1,2,4]

Brute Force Approach

For every day:

Move backward.
Count consecutive days having price less than or equal to the current day's price.
Stop when a larger price is encountered.

Example

for each day i
    move left until
    arr[j] > arr[i]

Complexity

O(n²)

Because each day may scan all previous days.

For:

n = 100000

this becomes too slow.

Key Observation

Suppose today's price is:

We don't care about all previous smaller prices individually.

We only need the nearest previous day having:

price > 90

Why?

Because that day blocks the span.

Everything between that day and today automatically belongs to the span.

Thus the problem becomes:

Find Previous Greater Element

for every index.

This is a classic Monotonic Stack problem.

Monotonic Stack Idea

Maintain a stack containing indices.

The stack stores days in decreasing order of stock prices.

For every new day:

Remove all smaller or equal prices

because they can never act as a boundary for future days.

After popping:

The stack top represents the nearest previous greater price.

Computing Span

Case 1

No greater element exists on the left.

Stack becomes empty

Then the span is:

i + 1

because every previous day belongs to the span.

Case 2

A greater element exists.

Let:

prevGreater = stack.top()

Then:

span = i - prevGreater

Dry Run

Consider:

arr = [10, 4, 5, 90, 120, 80]

Day 0

Price:

Stack:

[0]

Span:

Day 1

Price:

Previous greater:

Span:

Stack:

[0,1]

Day 2

Price:

Remove:

Previous greater:

Span:

Stack:

[0,2]

Day 3

Price:

Remove:

5
10

Stack becomes empty.

Span:

Day 4

Price:

Remove:

Stack becomes empty.

Span:

Day 5

Price:

Previous greater:

Span:

Final Answer

[1,1,2,4,5,1]

Why Monotonic Stack Works

Whenever a larger price arrives:

Smaller prices lose their importance

because they can never be the nearest greater element for future days.

Thus they are permanently removed.

Each index:

Push → once
Pop  → once

Therefore, total operations are linear.

C++ Solution

class Solution {
public:
    vector<int> calculateSpan(vector<int>& arr) {

        int n = arr.size();

        vector<int> span(n);

        stack<int> st;

        for(int i = 0; i < n; i++) {

            while(!st.empty() &&
                  arr[st.top()] <= arr[i]) {
                st.pop();
            }

            if(st.empty())
                span[i] = i + 1;
            else
                span[i] = i - st.top();

            st.push(i);
        }

        return span;
    }
};

Alternative Interpretation

Instead of saying:

Count consecutive smaller prices

you can think:

Find nearest previous greater price

Once that greater price is known:

Span =
Current Index - Previous Greater Index

This viewpoint makes the stack solution very intuitive.

Complexity Analysis

Time Complexity

O(n)

Each index is pushed and popped at most once.

Space Complexity

O(n)

for the stack.

Pattern Recognition

Whenever you see:

Previous Greater Element
Next Greater Element
Stock Span
Daily Temperatures
Histogram Problems
Visibility Problems
Nearest Larger Element

Think:

Monotonic Stack

These problems often reduce from:

O(n²)

to:

O(n)

using the same stack technique.

Key Takeaway

The Stock Span Problem is fundamentally a Previous Greater Element problem.

For every day, we find the nearest previous day having a strictly greater stock price. The distance between the current day and that boundary gives the span.

Using a monotonic decreasing stack allows us to process all days in linear time, making it one of the most important applications of the Monotonic Stack pattern.

Summary

The Stock Span Problem can be efficiently solved using a monotonic decreasing stack. Instead of checking all previous days, we find the nearest previous day with a greater stock price. This transforms a quadratic-time solution into a linear-time solution, making it suitable for large datasets and serving as a classic example of the Monotonic Stack pattern.