Online Stock Span: Coding Problem Solution

Source: Dev.to

Problem Overview

Online Stock Span is a streaming‑style problem that tests whether you can process data incrementally while keeping past information in a smart, compressed form. You are given daily stock prices one at a time, and for each new price, you must compute its span.

The span of a stock’s price on a given day is defined as the number of consecutive days (including today) for which the price has been less than or equal to today’s price.
For example, if today’s price is higher than yesterday’s and the day before yesterday, the span includes all of those days. If today’s price is lower than yesterday’s, the span is just 1.

The key constraint is that this is an online problem. You cannot see future prices, and you must answer each query as it arrives. That’s what makes it different from classic array‑based stock problems.

Why a naive approach breaks down

A straightforward approach is to look backward from today and count how many consecutive previous prices are smaller than or equal to the current price.
That works for a single day, but if prices keep increasing, you end up scanning farther and farther back every time. In the worst case, this leads to quadratic time behavior.

Interviewers use this problem to see whether you can avoid repeated work and recognize patterns that allow you to “skip” unnecessary comparisons.

The key idea behind the solution

The core insight is that not all previous days are equally important.

If you have a previous day with a lower price, and there is a newer day with a higher price, the older day will never matter again on its own. It gets “covered” by the newer, higher price.

This observation leads directly to the idea of using a monotonic stack.

Want to explore more coding problem solutions? Check out the Binary Tree Zigzag Level Order Traversal and Binary Search Tree Iterator.

How the stack‑based approach works

1. Maintain a stack where each entry represents a previous day, storing:

   • the price
   • the span associated with that price
     The stack is kept in strictly decreasing order of prices from bottom to top.

2. When a new price arrives, start with a span of 1 for today.

3. Look at the top of the stack:

   • If the top price ≤ today’s price, today’s span includes all the days represented by that entry. Add its span to today’s span and pop the entry.
   • Repeat until the stack is empty or the top price > today’s price.

4. Push today’s price and its computed span onto the stack.

5. The span you just computed is the answer for today.

Why this works conceptually

Each stack entry represents a block of consecutive days that are all smaller than the price below them in the stack.
By popping and merging spans, you collapse many smaller days into a single entry. This prevents repeated scanning of the same days.

Each day’s price is pushed onto the stack once and popped at most once, guaranteeing efficiency even for long sequences of increasing prices.

Why this is efficient in practice

Although a single day might cause several pops from the stack, those pops do not repeat across days.
Over the entire sequence of prices, the total number of pushes and pops is linear. That means the average time per operation is constant, even though individual steps may look more complex.

This “amortized” efficiency is a concept interviewers often want to hear you explain.

Common mistakes candidates make

• Storing only prices and recomputing spans manually, which loses the benefit of compression.
• Misunderstanding the comparison condition: the problem explicitly says “less than or equal,” and using only “less than” produces incorrect results.
• Forgetting that this is an online problem and trying to preprocess the entire array, which misses the point of the question.