What is the brute force approach and complexity for Stock Span Problem?

For each day, step backwards while the price is ≤ today's with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Stock Span Problem?

Keep a stack of days with decreasing prices; pop everything ≤ today with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Stock Span Problem?

Look for key signals in the prompt: "days in a row, going backwards" indicates We need the distance to a boundary on the left — the first day that breaks the run.; "less than or equal to that day's price" indicates The run stops at the first **strictly greater** price → previous greater element, with `≤` being popped.; "span of every day" indicates We need this boundary for all n days, so it must be cheap each time → monotonic stack..

Stock Span Problem

Easy·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelMonotonic Stack (decreasing, previous greater) — span / dominance

Complexity:O(N²)→O(N)

Key Insight

Keep a stack of indices whose prices strictly decrease from bottom to top. For each day, pop every index whose price is ≤ today's. The top that is left is the closest earlier day with a higher price, so span = i − top (or i + 1 if the stack is empty). Then push today.

Core Validity Invariant

A day stays on the stack only while no later day has a price ≥ it. Such a later day hides it from everyone after, so it can never stop a span again.

Problem

You are given the price of a stock on n days in a row, in the array arr.

The span of a day is the number of days in a row, ending with that day and going backwards, on which the price was less than or equal to that day's price. The day itself always counts, so every span is at least 1.

Return the span of every day. Write it as vector<int> calculateSpan(vector<int>& arr).

Input

An integer array arr of length n: the price on each day.

Output

An array of n numbers: the span of each day, in order.

Example 1

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

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

On day 5 the price is 75. Going back: 60, 70, 60 are all ≤ 75, then 80 is higher. So the span is 4 (days 2, 3, 4 and 5). On day 6 the price is 85: everything back to 100 is ≤ 85, so the span is 6.

Example 2

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

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

On day 3 the price is 90, and all three earlier prices are lower, so the span is 4. On day 5 the price 80 is lower than the 120 just before it, so the span is 1.

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 10^5

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
When I walk backwards from day i, what exactly makes me stop?
2.
If I knew the index of that stopping day, how would I get the span from it?
3.
Does a price equal to today's stop the span, or is it counted?
4.
Day j is earlier than day i and has a lower (or equal) price. Can day j ever be the stopping day for a day after i?
5.
So which earlier days are still worth remembering at any moment?

Brute force approach

Idea

For each day i, start a counter at 1 and walk back one day at a time. Keep counting while the earlier price is ≤ arr[i]. Stop at the first higher price or at the start of the array.

Thinking process

1
The definition itself tells you what to do: go backwards and count.
2
Stop as soon as you see a price strictly higher than today's.
3
Do this for every day.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> calculateSpan(vector<int>& arr) {
        int n = arr.size();
        vector<int> span(n);

        for (int i = 0; i < n; i++) {
            // Count today, then walk back while the earlier price is <= today's.
            int count = 1;
            int j = i - 1;
            while (j >= 0 && arr[j] <= arr[i]) {
                count++;
                j--;
            }
            span[i] = count;
        }
        return span;
    }
};

class Solution {
    public int[] calculateSpan(int[] arr) {
        int n = arr.length;
        int[] span = new int[n];

        for (int i = 0; i < n; i++) {
            // Count today, then walk back while the earlier price is <= today's.
            int count = 1;
            int j = i - 1;
            while (j >= 0 && arr[j] <= arr[i]) {
                count++;
                j--;
            }
            span[i] = count;
        }
        return span;
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def calculateSpan(self, arr: List[int]) -> List[int]:
        n = len(arr)
        span = [0] * n

        for i in range(n):
            # Count today, then walk back while the earlier price is <= today's.
            count = 1
            j = i - 1
            while j >= 0 and arr[j] <= arr[i]:
                count += 1
                j -= 1
            span[i] = count

        return span

export function calculateSpan(arr: number[]): number[] {
    const n = arr.length;
    const span = new Array(n);

    for (let i = 0; i < n; i++) {
        // Count today, then walk back while the earlier price is <= today's.
        let count = 1;
        let j = i - 1;
        while (j >= 0 && arr[j] <= arr[i]) {
            count++;
            j--;
        }
        span[i] = count;
    }
    return span;
}

Complexity

Time O(N²)Space O(1)

The slow case is a rising price, e.g. [1, 2, 3, …, n]. Day i walks back over all i earlier days, so the total is about n²/2. With n = 10^5 that is 5·10^9 steps. Only O(1) extra memory besides the output.

Optimized approach

Idea

Start from brute force

Brute force walks backwards from every day until it finds a higher price, one day at a time.

Find the repeated work

Low prices that sit between two higher ones are walked over again and again by every later day. But once a higher (or equal) price has come after them, they can never be the place where a span stops — they are just in the way.

Define the state — what variables do I need?

st: vector<int> used as a stack of day indices. Their prices strictly decrease from bottom to top. These are the only days that can still stop a future span.
i: The day being processed now.
prevGreater: After popping, the top of the stack: the closest earlier day with a price strictly higher than arr[i]. −1 if there is none.

Define validity

A day stays on the stack only while no later day has a price ≥ it. Such a later day hides it from everyone after, so it can never stop a span again.

Define the transitions — when does each pointer move, and why is it safe?

The stack is not empty and arr[top] ≤ arr[i]

st.pop_back()

That day's price is not higher than today's, so it is inside today's span. For any later day, today is closer and at least as high, so today would stop the span first. The popped day is never needed again.

The stack is empty, or arr[top] > arr[i]

span[i] = i − (st.empty() ? −1 : st.back())

The top is the closest earlier day that is strictly higher. Everything between it and today was ≤ today (that is what we just popped, plus what they had popped before).

After recording the span

st.push_back(i)

Today might be the higher price that stops a later day's span.

What does the current window add to the answer?

Each day gets its answer right when it is processed: the distance back to the previous strictly higher price.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> calculateSpan(vector<int>& arr) {
        int n = arr.size();
        vector<int> span(n);
        // st stores INDICES. Their prices strictly decrease from bottom to top.
        vector<int> st;

        for (int i = 0; i < n; i++) {
            // Days with price <= today are inside today's span. They are also
            // hidden behind today for every later day, so pop them for good.
            while (!st.empty() && arr[st.back()] <= arr[i]) {
                st.pop_back();
            }
            // The top (if any) is the closest earlier day with a higher price.
            int prevGreater = st.empty() ? -1 : st.back();
            span[i] = i - prevGreater;
            st.push_back(i);
        }
        return span;
    }
};

import java.util.*;

class Solution {
    public int[] calculateSpan(int[] arr) {
        int n = arr.length;
        int[] span = new int[n];
        // st stores INDICES. Their prices strictly decrease from bottom to top.
        Deque<Integer> st = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // Days with price <= today are inside today's span. They are also
            // hidden behind today for every later day, so pop them for good.
            while (!st.isEmpty() && arr[st.peek()] <= arr[i]) {
                st.pop();
            }
            // The top (if any) is the closest earlier day with a higher price.
            int prevGreater = st.isEmpty() ? -1 : st.peek();
            span[i] = i - prevGreater;
            st.push(i);
        }
        return span;
    }
}

from typing import List, Dict, Tuple, Deque, Optional
from collections import deque

class Solution:
    def calculateSpan(self, arr: List[int]) -> List[int]:
        n = len(arr)
        span = [0] * n
        # st stores INDICES. Their prices strictly decrease from bottom to top.
        st: List[int] = []

        for i in range(n):
            # Days with price <= today are inside today's span. They are also
            # hidden behind today for every later day, so pop them for good.
            while st and arr[st[-1]] <= arr[i]:
                st.pop()
            # The top (if any) is the closest earlier day with a higher price.
            prev_greater = -1 if not st else st[-1]
            span[i] = i - prev_greater
            st.append(i)

        return span

export function calculateSpan(arr: number[]): number[] {
    const n = arr.length;
    const span = new Array(n);
    // st stores INDICES. Their prices strictly decrease from bottom to top.
    const st: number[] = [];

    for (let i = 0; i < n; i++) {
        // Days with price <= today are inside today's span. They are also
        // hidden behind today for every later day, so pop them for good.
        while (st.length > 0 && arr[st[st.length - 1]] <= arr[i]) {
            st.pop();
        }
        // The top (if any) is the closest earlier day with a higher price.
        const prevGreater = st.length === 0 ? -1 : st[st.length - 1];
        span[i] = i - prevGreater;
        st.push(i);
    }
    return span;
}

Complexity

Time O(N)Space O(N)

The inner while can pop many days at once, but every day is pushed once and popped at most once. So all the pops over the whole run add up to at most n.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each day, step backwards while the price is ≤ today's	O(N²)	O(1)
Optimal	Keep a stack of days with decreasing prices; pop everything ≤ today	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“days in a row, going backwards”We need the distance to a boundary on the left — the first day that breaks the run.
“less than or equal to that day's price”The run stops at the first **strictly greater** price → previous greater element, with `≤` being popped.
“span of every day”We need this boundary for all n days, so it must be cheap each time → monotonic stack.

For each element+how far back do the ≤ values go+stop at the previous strictly greater→Monotonic Stack (decreasing, previous greater) — span / dominance

This is the anchor of the span sub-pattern. It is the same decreasing stack as Next Greater Element, but read the other way: instead of recording an answer for the popped elements, we record the answer for the new element, using whatever is left on top. The span is just i − prevGreater. The next question (Online Stock Span) has no array to look back into, so it keeps the span inside the stack instead of an index.

Don't make this mistake

Popping only while the price is strictly smaller

✗ while (!st.empty() && arr[st.back()] < arr[i]) st.pop_back();

✓ while (!st.empty() && arr[st.back()] <= arr[i]) st.pop_back();

Equal prices are part of the span. With <, an equal price stays on the stack and stops the span too early: [5, 5, 5] would give [1, 1, 1] instead of [1, 2, 3].

Forgetting the empty-stack case

✗ span[i] = i - st.back();

✓ span[i] = st.empty() ? i + 1 : i - st.back();

If every earlier price is ≤ today, the stack is empty and the span covers all days from 0 to i, which is i + 1 days. Calling back() on an empty vector is undefined behaviour.

Storing prices instead of indices

✗ st.push_back(arr[i]);

✓ st.push_back(i);

The span is a distance, so you need to know where the higher price was. Store the index and read the price with arr[st.back()].

Recording the answer for the popped element

Pattern confusion with Next Greater Element: there, when arr[i] pops j, you record nge[j] = arr[i]. Here the question is about the previous greater of i, so the popped days get nothing — the answer for i comes from the top after all the pops.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Online Stock Span