What does it solve?
The span of a stock on day i is the number of consecutive days ending at i (today included) where the price was less than or equal to today's. It's the classic range question: how far back does today's price dominate?
Key insight: the span is just the distance to the previous greater element. Keep a decreasing stack of indices. On day i, pop every day with price ≤ today's (they're swallowed into today's span). If the stack empties, span = i + 1 (dominates from the start); otherwise span = i − top. Push i. Each index is pushed and popped once → O(N).
The core idea
stack = empty
for i in 0..n-1:
while stack && price[top] <= price[i]: pop
span[i] = stack ? i - top : i + 1
push i
Complexity
Each day is pushed once and popped at most once across the whole run. The inner while loop's total work is bounded by N, so the scan stays linear.
The stack holds at most N indices (a strictly decreasing price sequence), plus the span array.
Examples & edge cases
Step-by-step table
| Step | i | price[i] | Stack (prices) | Rule | Action | Span |
|---|
C++ implementation
#include <bits/stdc++.h> using namespace std; // Stock Span: for each day, count consecutive days back (incl. today) // whose price is <= today's. Span = distance to previous greater element. vector<int> stockSpan(vector<int>& price) { int n = price.size(); vector<int> span(n); stack<int> st; // indices, prices decreasing bottom -> top for (int i = 0; i < n; i++) { // pop all days with price <= today's: swallowed into today's span while (!st.empty() && price[st.top()] <= price[i]) st.pop(); // empty → dominates from day 0; else distance to previous greater span[i] = st.empty() ? (i + 1) : (i - st.top()); st.push(i); } return span; } int main() { vector<int> p = {100,80,60,70,60,75,85}; vector<int> s = stockSpan(p); for (int x : s) cout << x << " "; // 1 1 1 2 1 4 6 return 0; }
My Notes