DSA Tracker

Visualize

Stock Span Problem

Monotonic decreasing stack of previous-higher days

time O(n)space O(n)

The naive answer walks backwards from every day until it meets a higher price, which is quadratic when prices trend downwards. The observation that fixes it: a day's span ends at its previous STRICTLY higher day, so the only thing worth remembering about the past is the days that are still higher than everything after them. Those days form a decreasing stack. When a new price arrives, every day at or below it is popped — and popping is safe forever, because any later day that could see past a popped day would have been stopped by today's higher price first. Whatever is left on top is the previous higher day, so the span is just the index gap; an empty stack means today is a new running maximum and the span reaches day 0. Each index is pushed once and popped at most once, so the whole pass is linear.

Details

Animated on: prices = [100, 80, 60, 70, 60, 75, 85]. For each day report its span: how many consecutive days ending today (today included) had a price at or below today's price. Answer: [1, 1, 1, 2, 1, 4, 6].

Problem:Stock Span ProblemMedium

Monotonic decreasing stack of previous-higher days

step 1 / 9

100
[0]
80
[1]
60
[2]
70
[3]
60
[4]
75
[5]
85
[6]

prices=[100, 80, 60, 70, 60, 75, 85]. A day's span counts backwards from today while the price stays at or below today's — so the span stops at the first STRICTLY higher day to the left. Keep a stack of indices whose prices run downhill; a day buried under a higher one can never end anybody's span, so it is safe to throw away forever.

Pseudocode
1FUNCTION stockSpan(prices):
2  span <- EMPTY LIST
3  stack <- EMPTY
4  FOR i <- 0 TO LENGTH(prices) - 1:
5    WHILE stack NOT EMPTY AND prices[TOP(stack)] <= prices[i]:
6      POP stack
7    IF stack IS EMPTY:
8      APPEND i + 1 TO span
9    ELSE:
10      APPEND i - TOP(stack) TO span
11    PUSH i ONTO stack
12  RETURN span

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. prices=[100, 80, 60, 70, 60, 75, 85]. A day's span counts backwards from today while the price stays at or below today's — so the span stops at the first STRICTLY higher day to the left. Keep a stack of indices whose prices run downhill; a day buried under a higher one can never end anybody's span, so it is safe to throw away forever.
  2. Day 0, price 100. Nothing to the left is higher than 100, so the run reaches all the way back to day 0 and span=1. Spans so far: [1]. Still standing: [day 0 (100)].
  3. Day 1, price 80. Day 0 (100) is the first price STRICTLY above 80, so the run stops there and span = 1 - 0 = 1. Spans so far: [1, 1]. Still standing: [day 0 (100), day 1 (80)].
  4. Day 2, price 60. Day 1 (80) is the first price STRICTLY above 60, so the run stops there and span = 2 - 1 = 1. Spans so far: [1, 1, 1]. Still standing: [day 0 (100), day 1 (80), day 2 (60)].
  5. Day 3, price 70. Day 2 (60) is at or below 70, so it is swallowed by today's run and can never block a later day either — pop it. Day 1 (80) is the first price STRICTLY above 70, so the run stops there and span = 3 - 1 = 2. Spans so far: [1, 1, 1, 2]. Still standing: [day 0 (100), day 1 (80), day 3 (70)].
  6. Day 4, price 60. Day 3 (70) is the first price STRICTLY above 60, so the run stops there and span = 4 - 3 = 1. Spans so far: [1, 1, 1, 2, 1]. Still standing: [day 0 (100), day 1 (80), day 3 (70), day 4 (60)].
  7. Day 5, price 75. Day 4 (60) and day 3 (70) are at or below 75, so they are swallowed by today's run and can never block a later day either — pop them. Day 1 (80) is the first price STRICTLY above 75, so the run stops there and span = 5 - 1 = 4. Spans so far: [1, 1, 1, 2, 1, 4]. Still standing: [day 0 (100), day 1 (80), day 5 (75)].
  8. Day 6, price 85. Day 5 (75) and day 1 (80) are at or below 85, so they are swallowed by today's run and can never block a later day either — pop them. Day 0 (100) is the first price STRICTLY above 85, so the run stops there and span = 6 - 0 = 6. Spans so far: [1, 1, 1, 2, 1, 4, 6]. Still standing: [day 0 (100), day 6 (85)].
  9. Every day answered in one pass: spans = [1, 1, 1, 2, 1, 4, 6]. The 2 days left on the stack ([day 0 (100), day 6 (85)]) are exactly the running maxima — each one was never covered by a later price, which is why no day after them could ever look past them.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Stock Span Problem in the editorAll Stack problemsBack to roadmap