Stock Span Problem

Medium
1399.

Stock Span Problem

Stock Span Problem is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon, Microsoft, Adobe and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} prices
 * @return {number[]}
 */
var calculateSpan = function(prices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Stock Span Problem — Solution in Python, Java & C++

Stock Span Problem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and stack.

Stock Span Problem is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon, Microsoft, Adobe and Flipkart interviews.

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

Hints for Stock Span Problem

  1. Hint 1

    Walking back from every day costs O(n²) on a rising market. What can you forget once a higher price appears?

  2. Hint 2

    If day j has a price no higher than day i (and j < i), no later day can ever stop at j without also passing i.

  3. Hint 3

    Keep a stack of indices with strictly decreasing prices. Pop every index whose price is at most today's; the span reaches back to the index left on top (or to the start).

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

Java

public static int[] calculateSpan(int[] prices) {
    int n = prices.length;
    int[] spans = new int[n];
    int[] stack = new int[n];
    int top = 0;
    for (int i = 0; i < n; i++) {
        while (top > 0 && prices[stack[top - 1]] <= prices[i]) top--;
        spans[i] = top == 0 ? i + 1 : i - stack[top - 1];
        stack[top++] = i;
    }
    return spans;
}

C++

vector<int> calculateSpan(vector<int>& prices) {
    int n = prices.size();
    vector<int> spans(n);
    vector<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && prices[st.back()] <= prices[i]) st.pop_back();
        spans[i] = st.empty() ? i + 1 : i - st.back();
        st.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure