165. Stock Span Problem

Given n days of stock prices, find the 'span' of each day - the number of consecutive days ending at (and including) that day for which the price was less than or equal to that day's price. Print the spans, space-separated.

Input: The first line contains an integer n. The second line contains n space-separated integers representing the stock prices for each day. Output: Print n space-separated integers - the span of each day, in order.

1 <= n <= 10^5

Unlike Next Greater/Smaller Element (which scan right to left), Stock Span scans LEFT TO RIGHT, since each day's span depends only on days BEFORE it - the monotonic stack technique adapts naturally to either scan direction depending on what each problem asks for.

For each day's stock price, find how many CONSECUTIVE days (ending at and including today) had a price less than or equal to today's. Brute force: For every day, scan backward directly counting consecutive days with price <= today's - this costs O(n²) in the worst case, too slow for large price histories. Optimised: A monotonic stack of indices (holding only days that are still 'unbeaten' by anything since) lets each day's span be computed by popping all the now-irrelevant smaller/equal days at once - each index is pushed and popped at most once across the whole scan, giving O(n) total work.

Maintain a stack of day indices whose prices are in strictly decreasing order as you scan left to right. For each new day, pop every index off the stack whose price is less than or equal to the current price (those days can never again be the 'nearest greater' boundary for anything after this point), and the span is simply the current index minus the index now left on top of the stack (or the current index + 1 if the stack becomes empty). Push the current index and continue. Each index is pushed and popped from the stack at most once, so the total work across all n days is linear, which is optimal since every price must be examined at least once. Time: O(n) Space: O(n)

Split the array into blocks of size about sqrt(n) and store the maximum price within each block. To find the span for day i, walk backwards block by block: if an entire earlier block's maximum is still less than or equal to price[i], the whole block can be skipped in O(1) since none of its days can break the streak; only when a block might contain the breaking day do you fall back to scanning it element by element. This avoids re-examining every single earlier day one at a time and cuts the worst-case work down from linear-per-day to about sqrt(n)-per-day. Time: O(n sqrt n) Space: O(sqrt n)

For every day i, walk backwards day by day counting how many consecutive prior days (including day i itself) have a price less than or equal to price[i], stopping as soon as a strictly greater price is found. This directly implements the definition of span but repeats a lot of work: in the worst case (a strictly increasing price sequence) every day scans all the way back to day 0, giving quadratic total work. Time: O(n^2) Space: O(1)

1. Maintain a stack of INDICES of days whose prices are strictly greater than everything seen after them so far. 2. For each new day, pop every index whose price is <= today's price - those days are all 'covered' by today's span. 3. The span is (today's index minus the new stack top's index), or (today's index + 1) if the stack becomes completely empty; push today's index for future days to compare against.

Time: O(n) - each day's index is pushed and popped from the stack at most once. Space: O(n) in the worst case, for the stack.

n = 1 (span is always 1); a strictly decreasing price sequence (every span is 1) versus a strictly increasing one (spans grow to i+1); n up to 10^5 for performance.

Be ready to connect this directly to 'Next Greater Element to the Left' (a mirrored variant scanning left to right instead of right to left) - stock span is really just 'how far back until a strictly greater price', computed via the same monotonic-stack idea.