Stock Span Problem
A medium Stack problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Stack
- Sheets
- 3
- Core for
- 8 roles
- Platform
- GeeksforGeeks
The problem
Design an algorithm that collects daily stock price quotes and returns the stock span for each day. The stock span is the maximum number of consecutive days (up to and including the current day) where the price was less than or equal to the current day's price.
Example 1
- Input
- prices = [100,80,60,70,60,75,85]
- Output
- [1,1,1,2,1,4,6]
- Why
- Day 3 (price 70) has span 2 because the previous day (60) was <= 70 but the day before that (80) was not. Day 6 (price 85) has span 6 because all previous prices were <= 85.
Example 2
- Input
- prices = [10,4,5,90,120,125]
- Output
- [1,1,2,4,5,6]
- Why
- Day 3 (90) spans 4 days back since all prices before it (except 10) were <= 90. Day 5 (125) spans 6.
Constraints
- 1 <= prices.length <= 10^5
- 1 <= prices[i] <= 10^5
How to think about it
Updated 2026-09-09Every incoming price swallows all earlier consecutive days whose prices were smaller or equal. Instead of retaining those drowned days individually, absorb them into the new day: store each price alongside the span it has already accumulated. When a new price beats the top, it takes that top's span and continues looking deeper.
Approaches, worst first
Scan backward on every next call
time O(n^2) · space O(n)
Keep an append-only array of all past prices. On each call with price p, step backward from the latest entry toward the beginning until encountering a price strictly greater than p. Degrades to quadratic cumulative time when quotes arrive in non-decreasing order.
Monotonic decreasing stack of price-span pairsWrite this one
time O(n) · space O(n)
Maintain a stack storing pairs `(price, span)`. For each incoming price, initialize `span = 1`. While the stack is non-empty and `stack.top().price <= price`, pop the top and add its span to the running span. Push `(price, span)` and return it. Each price enters and leaves the stack at most once.
Where people lose marks · 2
- Discarding the span of popped elements: you cannot just count how many items you pop, because previously popped items may themselves represent spans spanning dozens of days.
- Using `<` instead of `<=`: prices equal to the current day must count toward the span.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
What each operation costs
| Operation | Time |
|---|---|
| push item onto the top | O(1) |
| pop item from the top | O(1) |
| inspect the topmost element | O(1) |
What usually goes wrong with Stack
- Popping from or peeking into an empty stack without first verifying that the size is positive, causing runtime null pointer or empty collection errors.
- Forgetting to verify that the stack is completely empty at the end of bracket matching, which mistakenly accepts strings with dangling unclosed opening symbols.
- Storing values instead of indices in monotonic stacks, making it impossible to calculate distance intervals between matching elements afterwards.
Which roles need this problem
Stack is a core topic for these 8 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 9 more roles, including Frontend Engineer, Data Engineer, Game Developer.
Companies that have asked it
Tags taken from the problem's own GeeksforGeeks page — not a copied list.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Stack problems
Problem set and role mapping as of .