☕ DSA Java Articles

Topics › Stacks and Queues › Implementation Problems

Stock span problem

Hard TUF ID 964 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the daily prices of a stock, prices[0..n-1]. The span of day i is the number of consecutive days ending at day i (counting day i itself) on which the price was less than or equal to prices[i]. Return the span of every day.

The LeetCode version (Online Stock Span) is the same question asked online: a StockSpanner object receives one price per call to next(price) and must return that day’s span immediately, without seeing the future.

Constraints: 1 ≤ n ≤ 10^5, 1 ≤ prices[i] ≤ 10^5.

Example 1

prices = [100, 80, 60, 70, 60, 75, 85]
spans  = [  1,  1,  1,  2,  1,  4,  6]
// day 5 (75): 75, 60, 70, 60 are all <= 75, then 80 stops the run -> 4
// day 6 (85): 85, 75, 60, 70, 60, 80 are all <= 85, then 100 stops it -> 6

Example 2

prices = [10, 4, 5, 90, 120, 80]
spans  = [ 1, 1, 2,  4,   5, 1]

Restating the question. Walking left from day i, the run stops at the first day with a price strictly greater than prices[i]. If that day is p (or -1 if there is none), the span is i - p. So this is the previous greater element problem in disguise.

Approach 1: Brute force

Intuition. Do what the definition says: from each day, walk left while the price is not higher, and count the steps.

Algorithm.

  1. For each day i, start with j = i.
  2. While j ≥ 0 and prices[j] ≤ prices[i], decrement j.
  3. The span is i - j (j is now the previous greater day, or -1).
static int[] bruteForce(int[] prices) {
    int n = prices.length;
    int[] span = new int[n];
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j >= 0 && prices[j] <= prices[i]) j--;
        span[i] = i - j;                          // j is the previous greater day, or -1
    }
    return span;
}

Complexity. Time O(n^2) in the worst case: for an increasing price list, day i walks all the way back to day 0. Space O(1) besides the output.

Approach 2: Optimal, previous greater element with a monotonic stack

Intuition. When we walk left from day i, many days are pointless to visit. Suppose day j < i has prices[j] ≤ prices[i]. For any later day t > i, the walk from t either stops at day i or goes past it. If it goes past day i, then prices[t] ≥ prices[i] ≥ prices[j], so it also goes past day j. Either way, day j can never be the stopping point for any later day. Day i shadows it.

So keep only the days that are not shadowed. They form a stack of indices whose prices are strictly decreasing from bottom to top. For a new day i:

Algorithm.

  1. For each day i: pop while prices[top] ≤ prices[i].
  2. span[i] = i + 1 if the stack is empty, else i - top.
  3. Push i.
static int[] optimal(int[] prices) {
    int n = prices.length;
    int[] span = new int[n];
    Deque<Integer> st = new ArrayDeque<>();      // indices whose prices strictly decrease from bottom to top
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && prices[st.peek()] <= prices[i]) st.pop();
        span[i] = st.isEmpty() ? i + 1 : i - st.peek();
        st.push(i);
    }
    return span;
}

Complexity. Time O(n): each index is pushed once and popped at most once, so the total work of all the while loops is bounded by n. Space O(n) for the stack in the worst case (strictly decreasing prices).

Approach 3: Online, store spans on the stack

Intuition. In the online version we do not have an array of past prices to index into. We can still keep the same stack; we just store, for each surviving day, the pair {price, span} instead of an index.

Here is why the span is enough. When day i pops an entry {price, span}, that entry stands for a whole block of consecutive days: the popped day plus the span - 1 days it had absorbed, all with prices ≤ price ≤ prices[i]. So day i’s span grows by that entry’s entire span at once. Starting from 1 (day i itself) and adding the spans of everything popped gives exactly the length of the run.

Algorithm.

  1. next(price): set span = 1.
  2. While the top’s price is ≤ price, pop it and add its span to span.
  3. Push {price, span} and return span.
static class StockSpanner {
    private final Deque<int[]> st = new ArrayDeque<>();   // {price, span}

    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;
    }
}

static int[] online(int[] prices) {
    StockSpanner spanner = new StockSpanner();
    int[] span = new int[prices.length];
    for (int i = 0; i < prices.length; i++) span[i] = spanner.next(prices[i]);
    return span;
}

The helper online(prices) simply feeds an array through a fresh StockSpanner so the three approaches can be tested against the same expected output.

Dry run on Example 1 with the online spanner (stack shown bottom to top as price:span):

price popped entries span stack after
100 none 1 100:1
80 none 1 100:1, 80:1
60 none 1 100:1, 80:1, 60:1
70 60:1 1 + 1 = 2 100:1, 80:1, 70:2
60 none 1 100:1, 80:1, 70:2, 60:1
75 60:1, 70:2 1 + 1 + 2 = 4 100:1, 80:1, 75:4
85 75:4, 80:1 1 + 4 + 1 = 6 100:1, 85:6

Complexity. Each call is O(1) amortised: across all calls, each price is pushed once and popped at most once. Space O(n) for the stack.

Edge cases and pitfalls