Stock Span Problem — Medium Problem & Solution

Problem statement

prices[i] is the closing price of a share on day i. The span of day i is the number of consecutive days, ending with day i itself and walking backwards, on which the price was less than or equal to the price of day i.

So the span is always at least 1 (the day itself), and it stops growing at the first earlier day whose price is strictly higher.

Return an array holding the span of every day.

Example 1

Input: prices = [100,80,60,70,60,75,85]
Output: [1,1,1,2,1,4,6]
Explanation: Day 5 (price 75) reaches back over 60, 70 and 60 and stops at 80, so its span is 4.

Example 2

Input: prices = [10,4,5,90,120,80]
Output: [1,1,2,4,5,1]

Example 3

Input: prices = [5,5,5]
Output: [1,2,3]
Explanation: Equal prices do not stop the span.

Constraints

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

How to solve Stock Span Problem

The span of day i ends at the nearest earlier day with a strictly higher price — the previous greater element — which a monotonic stack finds for all days in one pass.

Approach

1. Keep a stack of day indices whose prices are strictly decreasing from bottom to top.
2. For day i, pop every index whose price is less than or equal to prices[i].
3. If the stack is now empty, every earlier day was no higher, so the span is i + 1; otherwise it is i - top.
4. Push i and continue.

Why it works

A popped day j has prices[j] <= prices[i] with j < i. Any later day that walks back far enough to reach j must first pass i, and it would stop at i already if prices[i] were higher than its own price — so j can never be the stopping point again. What remains on the stack is exactly the set of candidate stopping points, and the top one is the nearest.

Complexity

• Time — O(n) — every index is pushed and popped at most once
• Space — O(n)

Pitfalls

• Pop on <=, not <: an equal price belongs to the span.
• Store indices, not prices, so the span is a subtraction.
• When the stack empties the span covers every day so far: i + 1, not i.

Reference solution

Python

from typing import List

def calculateSpan(prices: List[int]) -> List[int]:
    stack = []
    spans = []
    for i, p in enumerate(prices):
        while stack and prices[stack[-1]] <= p:
            stack.pop()
        spans.append(i + 1 if not stack else i - stack[-1])
        stack.append(i)
    return spans

JavaScript

var calculateSpan = function(prices) {
    var stack = [];
    var spans = [];
    for (var i = 0; i < prices.length; i++) {
        while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) stack.pop();
        spans.push(stack.length === 0 ? i + 1 : i - stack[stack.length - 1]);
        stack.push(i);
    }
    return spans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium