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

Code
[100, 80, 90, 120]

Output

Code
[1, 1, 2, 4]

Understanding the Span

Consider:

Prices

Code
[100, 80, 90, 120]

Day 0

Price:

Code
100

No previous day exists.

Span:

Code
1

Day 1

Price:

Code
80

Previous price:

Code
100 > 80

Span:

Code
1

Day 2

Price:

Code
90

Previous prices:

Code
80 <= 90
100 > 90

Span:

Code
2

Day 3

Price:

Code
120

Previous prices:

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

Span:

Code
4

Final Answer

Code
[1,1,2,4]

Brute Force Approach

For every day:

  1. Move backward.

  2. Count consecutive days having price less than or equal to the current day's price.

  3. Stop when a larger price is encountered.

Example

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

Complexity

Code
O(n²)

Because each day may scan all previous days.

For:

Code
n = 100000

this becomes too slow.

Key Observation

Suppose today's price is:

Code
90

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

We only need the nearest previous day having:

Code
price > 90

Why?

Because that day blocks the span.

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

Thus the problem becomes:

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

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

Code
Stack becomes empty

Then the span is:

Code
i + 1

because every previous day belongs to the span.

Case 2

A greater element exists.

Let:

Code
prevGreater = stack.top()

Then:

Code
span = i - prevGreater

Dry Run

Consider:

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

Day 0

Price:

Code
10

Stack:

Code
[0]

Span:

Code
1

Day 1

Price:

Code
4

Previous greater:

Code
10

Span:

Code
1

Stack:

Code
[0,1]

Day 2

Price:

Code
5

Remove:

Code
4

Previous greater:

Code
10

Span:

Code
2

Stack:

Code
[0,2]

Day 3

Price:

Code
90

Remove:

Code
5
10

Stack becomes empty.

Span:

Code
4

Day 4

Price:

Code
120

Remove:

Code
90

Stack becomes empty.

Span:

Code
5

Day 5

Price:

Code
80

Previous greater:

Code
120

Span:

Code
1

Final Answer

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

Why Monotonic Stack Works

Whenever a larger price arrives:

Code
Smaller prices lose their importance

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

Thus they are permanently removed.

Each index:

Code
Push → once
Pop  → once

Therefore, total operations are linear.

C++ Solution

C++
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:

Code
Count consecutive smaller prices

you can think:

Code
Find nearest previous greater price

Once that greater price is known:

Code
Span =
Current Index - Previous Greater Index

This viewpoint makes the stack solution very intuitive.

Complexity Analysis

Time Complexity

Code
O(n)

Each index is pushed and popped at most once.

Space Complexity

Code
O(n)

for the stack.

Pattern Recognition

Whenever you see:

Think:

Code
Monotonic Stack

These problems often reduce from:

Code
O(n²)

to:

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