The Stock Span Problem

If the balanced-brackets problem is where most people fall in love with stacks, the stock span problem is where they discover a second, deeper trick — the monotonic stack. It looks like a finance question, but hidden inside it is a pattern so useful that once you learn it, a whole family of "hard" problems suddenly become easy.

So let us sit together, understand what is being asked, and slowly build our way from the brute-force answer to the elegant O(n) solution.

The Problem

Imagine you are tracking the daily price of a stock. For each day, we want to calculate its span.

The span of a day is defined as: the number of consecutive days ending on that day (going backwards) for which the price was less than or equal to the price on that day.

Let us make that concrete. Say the prices are:

Day:    0    1    2    3    4    5    6
Price: 100   80   60   70   60   75   85

The spans work out to [1, 1, 1, 2, 1, 4, 6]. Let us understand a couple of them:

• Day 0 (price 100): there are no earlier days, so the span is just 1 (today itself).
• Day 3 (price 70): today counts as 1. Yesterday was 60, which is ≤ 70, so that counts too. The day before was 80, which is bigger than 70 — so we stop. Span = 2.
• Day 6 (price 85): today, plus 75, plus 60, plus 70, plus 60... it keeps going back until it hits 100 on day 0, which is bigger. Span = 6.

So essentially, for each day we are asking: "Going backwards, how far can I travel before I meet a price higher than today's?"

The Brute-Force Idea (and Why We Want Better)

The obvious solution is, for every day, walk backwards and count until you hit a bigger price:

function calculateSpanBrute(prices) {
    let span = [];
    for (let i = 0; i < prices.length; i++) {
        let count = 1;
        let j = i - 1;
        while (j >= 0 && prices[j] <= prices[i]) {
            count++;
            j--;
        }
        span.push(count);
    }
    return span;
}

This is correct and easy to understand. But in the worst case — imagine prices that keep increasing, like [10, 20, 30, 40] — every day walks all the way back to the start. That is O(n²). For large inputs, this is too slow, and the interviewer will gently ask, "Can you do better?"

Yes. We can do it in a single pass. This is where the stack enters.

The Key Insight

Here is the observation that changes everything. When we are standing on day i, which earlier days do we actually care about?

Look again at day 6 (price 85). To find its span, we needed to skip past all the smaller prices (75, 60, 70, 60) and stop at the first price that was strictly greater (100 on day 0). So the only price that mattered was the nearest earlier day whose price was greater than today's.

That gives us the real question hiding inside this problem:

For each day, find the nearest previous day with a strictly greater price. The span is simply the distance to that day.

And notice something lovely: once a day's price is "buried" under a newer, higher price, it can never be the answer for any future day — because that future day would stop at the higher price first. So we can throw those buried days away. That is exactly what a monotonic stack does: it keeps only the useful candidates, in decreasing order of price.

The Elegant O(n) Solution

We will keep a stack of indices, arranged so that the prices they point to are in decreasing order. For each new day, we pop away everything that is smaller-or-equal (those days are now useless), and whatever remains on top is our "nearest greater price" day.

function calculateSpan(prices) {
    let n = prices.length;
    let span = new Array(n);
    let stack = []; // stores indices; the prices they point to stay in decreasing order

    for (let i = 0; i < n; i++) {
        // pop every earlier day whose price is <= today's price
        // (those days can never be a "greater price" barrier again)
        while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
            stack.pop();
        }

        // if the stack is now empty, no earlier day had a greater price,
        // so the span is the whole stretch from day 0 up to today
        span[i] = stack.length === 0 ? (i + 1) : (i - stack[stack.length - 1]);

        // today becomes a candidate barrier for future days
        stack.push(i);
    }

    return span;
}

let prices = [100, 80, 60, 70, 60, 75, 85];
console.log(calculateSpan(prices)); // [1, 1, 1, 2, 1, 4, 6]

Walking Through the Code

Let us not run away after pasting. Let us feel what the stack is doing.

Why store indices, not prices?

Because the span is a distance — we need to know how many days back the greater price sits, not just its value. With indices, the distance is a simple subtraction: i - stack.top().

The while loop:

while (stack.length > 0 && 
       prices[stack[stack.length - 1]] <= prices[i]) {
    stack.pop();
}

This pops every earlier day whose price is less than or equal to today's. Think about why this is safe: if an old day's price is not greater than today's, then today "covers" it — no future day will ever be stopped by that old day, because it would run into today first. So we discard it forever.

Computing the span:

span[i] = stack.length === 0 ? (i + 1) : (i - stack[stack.length - 1]);

Two cases:

• If the stack is empty, it means every earlier day had a price ≤ today's. So today's span reaches all the way back to day 0. That distance is i + 1 (remember, day indices start at 0).
• Otherwise, the top of the stack is the nearest earlier day with a strictly greater price — our barrier. The span is simply i - (that index).

Finally, push today:

stack.push(i);

Today now becomes a potential barrier for the days that come after it.

Let Us Trace It

Prices [100, 80, 60, 70, 60, 75, 85]. Watch the stack (I will show the indices it holds):

Result: [1, 1, 1, 2, 1, 4, 6]. Exactly what we expected — and we never walked backwards manually even once.

Why Is This O(n)?

At first glance the while loop inside a for loop looks like O(n²). But look closer: each index is pushed onto the stack exactly once, and popped at most once. Across the entire run, the total number of push and pop operations is at most 2n. So the whole algorithm is O(n) time. This "amortised" reasoning is a favourite interview follow-up, so be ready to explain it.

• Time: O(n) — each element is pushed and popped at most once.
• Space: O(n) — in the worst case (strictly decreasing prices), the stack holds every index.

Final Thoughts

The stock span problem is really the "next greater element" problem wearing a business suit. And that pattern — use a stack to keep only the useful candidates, throwing away anything a newer element makes irrelevant — is the monotonic stack. Once it clicks here, you will recognise it in daily temperatures, in the largest rectangle in a histogram, in trapping rain water, and in many more.

Learn this one idea deeply, and you have not solved one problem — you have unlocked a whole shelf of them.

Happy coding, and all the best for your interviews!