Online Stock Span - Practice Coding Problems

Online Stock Span - Problem

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.

The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

For example:

If the prices in the last four days were [7,2,1,2] and today's price is 2, then the span is 4 because all 4 consecutive days had prices ≤ 2.
If the prices in the last four days were [7,34,1,2] and today's price is 8, then the span is 3 because the last 3 days had prices ≤ 8 (but day 4 had price 34 > 8).

Implement the StockSpanner class:

StockSpanner() Initializes the object
int next(int price) Returns the span of the stock's price given that today's price is price

Input & Output

Example 1 — Basic Stock Prices

$ Input: prices = [100,80,60,70,60,75,85]

› Output: [1,1,1,2,1,4,6]

💡 Note: Day 1: price=100, span=1 (just today). Day 2: price=80, span=1 (80<100). Day 3: price=60, span=1 (60<80). Day 4: price=70, span=2 (70≥60, 70<80). Day 5: price=60, span=1 (60<70). Day 6: price=75, span=4 (75≥60,70,60, 75<80). Day 7: price=85, span=6 (85≥75,60,70,60,80, 85<100).

Example 2 — Increasing Prices

$ Input: prices = [10,20,30,40]

› Output: [1,2,3,4]

💡 Note: Each day has a higher price, so the span includes all previous days plus today.

Example 3 — Decreasing Prices

$ Input: prices = [40,30,20,10]

› Output: [1,1,1,1]

💡 Note: Each day has a lower price than the previous, so span is always 1 (just today).

Constraints

1 ≤ prices.length ≤ 10⁴
1 ≤ prices[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Stream of daily stock prices: [100,80,60,70,60,75,85]

Process

For each price, count consecutive days ≤ current price

Output

Spans: [1,1,1,2,1,4,6]

Key Takeaway

🎯 Key Insight: Use a monotonic stack to skip irrelevant days and achieve O(1) amortized time per query

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is using a monotonic stack to eliminate redundant comparisons. Instead of scanning back through all previous prices for each query, we maintain a stack that only keeps prices greater than those we've seen. Best approach is the stack solution with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack - Skip Irrelevant Days	O(n)	O(n)	Use a stack to remember only days with higher prices, skipping over smaller ones
Brute Force - Look Back Every Time	O(n²)	O(n)	For each new price, scan backwards through all previous prices

Monotonic Stack - Skip Irrelevant Days — Algorithm Steps

Pop all stack elements with price ≤ current price
Sum up the spans of popped elements
Push current (price, accumulated_span) to stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Pop Smaller Prices

Remove all stack entries with price ≤ current

Accumulate Spans

Add spans of popped elements to current span

Push New Entry

Add (current_price, total_span) to stack

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int price;
    int span;
} Pair;

typedef struct {
    Pair* stack;
    int top;
    int capacity;
} StockSpanner;

StockSpanner* stockSpannerCreate() {
    StockSpanner* spanner = (StockSpanner*)malloc(sizeof(StockSpanner));
    spanner->stack = (Pair*)malloc(1000 * sizeof(Pair));
    spanner->top = -1;
    spanner->capacity = 1000;
    return spanner;
}

int stockSpannerNext(StockSpanner* obj, int price) {
    int span = 1;
    // Pop all prices <= current price and accumulate their spans
    while (obj->top >= 0 && obj->stack[obj->top].price <= price) {
        span += obj->stack[obj->top].span;
        obj->top--;
    }
    
    obj->top++;
    obj->stack[obj->top].price = price;
    obj->stack[obj->top].span = span;
    return span;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int prices[1000];
    int count = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        prices[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    StockSpanner* spanner = stockSpannerCreate();
    printf("[");
    for (int i = 0; i < count; i++) {
        int span = stockSpannerNext(spanner, prices[i]);
        printf("%d", span);
        if (i < count - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each price is pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n price-span pairs in worst case

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack - Skip Irrelevant Days — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler