The O(n) Club: Stock Span, Stacks, and the Brute-Force Blues

The O(n) Club: Stock Span, Stacks, and the Brute-Force Blues

⚡ TL;DR

Every day, a stock price appears. For each, report how many days in a row (up to today) it hasn’t been beaten. If you scan back over all history, your CPU will cry. Stack to the rescue:

// Brute force (your CPU will issue a restraining order)
public int next(int price) {
    int span = 1;
    for (int i = prices.size() - 1; i >= 0 && prices.get(i) <= price; i--) {
        span++;
    }
    prices.add(price);
    return span;
}

🧠 How Devs Usually Mess This Up

Let’s be honest—most of us start by crawling backward through every old price, counting how long we can withstand the FOMO. This is fine if you’re coding for your Tamagotchi, but the moment you plug this into a real data stream, OJ (that’s Online Judge, not orange juice) slaps you with a TLE. Mess it up more by trying a stack but only pushing prices, not their spans, and soon you’ll be writing code that confuses even Stack Overflow.

🔍 What’s Actually Going On

Think of your price history as a medieval queue for bread. Each new price shoves weaker prices (and their friends) out of the way. The monotonic stack holds only the last line of resistance, and each pop aggregates streaks of conquered peasants (er, prices). Today’s price? It absorbs any streak it just dominated: just pop and tally up until you find someone taller (or the well is dry).

🛠️ PseudoCode

• Set up: Use a stack of pairs (price, span).
• Arrival: New price walks in, span starts at 1 (today counts itself—it’s not that humble).
• Pop and conquer: While stack is not empty && top price ≤ today, pop and add its span to your own, because you just obliterated their streak.
• Push yourself: Add (price, span) to the stack—own your legacy.
• Return: Hand the span back to whoever asked for it (probably an overworked product manager).

// Pseudo-Javaish
int span = 1;
while (!stack.isEmpty() && stack.peek().price <= price) {
    span += stack.pop().span;
}
stack.push(new Pair(price, span));
return span;

💻 The Code

import java.util.*;
 class StockSpanner {
    private static class Pair {
        int price, span;
        Pair(int price, int span) {
            this.price = price;
            this.span = span;
        }
    }
    private Deque
<pair> stack = new ArrayDeque<>();
     public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek().price <= price) {
            span += stack.pop().span;
        }
        stack.push(new Pair(price, span));
        return span;
    }
}
</pair>

⚠️ Pitfalls, Traps & Runtime Smacks

• O(n) blues: Loop-all-the-way-back solutions are slow enough to make day trading look safe. Amortized O(1) is the stack’s superpower.
• Forgetting spans: If you only store prices, you’ll get lost in your own stack forest. Always record span with the price.
• Space: Worst case, the stack reaches O(n) if every price is smaller than before. It’s never O(n²), so don’t call your algorithm professor in a panic.
• Shaky Data: Prices trending downward? You have lots of stack, but you’re still O(1) time per call over the long haul.

🧠 Interviewer Brain-Tattoo

“Every time you brute-force yesterday’s prices, a monotonic stack developer gets a wrinkle. Pop and conquer.”