Skip to main content
Monotonic Stack

Stock Span

For each day, count how many consecutive previous days had a price ≤ today. A decreasing stack of prices (storing indices) gives the span instantly when you pop all smaller prices.

O(n)
·
O(n)

How It Works

The stock span asks, for each day, how many consecutive prior days had a price less than or equal to today's. Equivalently, it is the distance back to the previous strictly greater price. A decreasing monotonic stack of indices delivers this directly: when today's price arrives, pop every index whose price is less than or equal to it. The span is today's index minus the index now on top of the stack (or the full length if the stack empties).

The naive method walks backward from each day, costing O(n²) on rising sequences. Since every day is pushed once and popped at most once, the stack computes all spans in amortized O(1) per day, O(n) total.

Step-by-Step Visualization

Stock span: consecutive days with price ≤ today
Input
100
80
60
70
60
75
85
Stack
100:1
Span[1]
1/5

Code

Java
static int[] stockSpan(int[] prices) {
  int[] spans = new int[prices.length];
  Stack<int[]> stack = new Stack<>(); // [price, span]

  for (int i = 0; i < prices.length; i++) {
    int span = 1;
    while (!stack.isEmpty() && stack.peek()[0] <= prices[i]) {
      span += stack.pop()[1];
    }
    stack.push(new int[]{prices[i], span});
    spans[i] = span;
  }
  return spans;
}

// Example: [100,80,60,70,60,75,85] → [1,1,1,2,1,4,6]

Tips & Gotchas

1Stock span = count of consecutive days with price ≤ today
2Use a decreasing stack of (price, span) or indices
3When current price ≥ stack top, accumulate that span

Practice Problems

  • 1Online Stock Span
  • 2Daily Temperatures
  • 3Sum of Subarray Minimums

About the Monotonic Stack Pattern

Keep the stack in sorted order (always increasing or always decreasing). When a new element would break the order, pop elements until the order is restored. Each popped element just found its 'answer' (the element that caused the pop).

Key insight

Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).

Common Stack Interview Problems

  • Valid Parentheses
  • Next Greater Element
  • Largest Rectangle in Histogram
  • Trapping Rain Water
  • Daily Temperatures
  • Decode String

Frequently Asked Questions

How is stock span related to next greater element?

It is the mirror image: span looks for the previous greater element instead of the next one. The same decreasing stack works, but you compute the answer at push time (distance to the surviving stack top) rather than at pop time.

Why pop on less-than-or-equal rather than strictly less?

Days with equal prices count toward the span, so they must be absorbed. Popping equal prices also keeps the stack strictly decreasing, which caps its size and preserves the amortized O(1) bound in streaming settings like Online Stock Span.