Crack the Backend

Problem Statement

Design a structure that receives a stream of daily stock prices. Each time next(price) is called, it means today's price is price. Return the span of the current day: the maximum number of consecutive days (including today) for which the price was less than or equal to today's price.

Key Observations

Monotonic stack: We store pairs (price, span). When we see a new price, we need to count how many previous days have price <= current. Those form a contiguous segment (the "span"). So: start with span = 1; while the stack is not empty and the top price is <= current price, pop and add the popped span to our span (all those days are in our consecutive segment). Then push (price, span) and return span. The stack keeps (price, span) in decreasing order of price (we've "compressed" consecutive smaller days into one entry).

Approach

High-level: Stack of (price, span). next(price): span = 1; while stack not empty and stack.peek()[0] <= price, span += stack.pop()[1]; stack.push(new int[]{price, span}); return span.

Steps: Deque<int[]> st (price, span). In next(price): int span = 1; while (!st.isEmpty() && st.peek()[0] <= price) span += st.pop()[1]; st.push(new int[]{price, span}); return span.

Implementation

Java

Deque<int[]> st = new ArrayDeque<>();

public int next(int price) {
    int span = 1;

    while (!st.isEmpty() && st.peek()[0] <= price) {
        span += st.pop()[1];
    }

    st.push(new int[]{price, span});
    return span;
}

Test Cases

Example

Input

prices = [100,80,60,70,60,75,85]

Expected

[1,1,1,2,1,4,6]

Explanation

Span for each day.

Complexity Analysis

Time: O(n).
Space: O(n) for stack.

Follow-ups

Previous smaller; range queries.