Pattern visualizer
Stock Span Problem
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. 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]..
Monotonic decreasing stack of previous-higher days
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.
1FUNCTION stockSpan(prices):2 span <- EMPTY LIST3 stack <- EMPTY4 FOR i <- 0 TO LENGTH(prices) - 1:5 WHILE stack NOT EMPTY AND prices[TOP(stack)] <= prices[i]:6 POP stack7 IF stack IS EMPTY:8 APPEND i + 1 TO span9 ELSE:10 APPEND i - TOP(stack) TO span11 PUSH i ONTO stack12 RETURN span
← / → step · space play · Home restart