901. Online Stock Span

NeetCode: Online Stock Span · LeetCode: 901. Online Stock Span · Difficulty: Medium

Design a class StockSpanner with a method next(price) that receives today's price and returns its span: the maximum number of consecutive days (starting from today and going backwards) for which the price was less than or equal to today's price.

Example

next(100) -> 1
next(80)  -> 1
next(60)  -> 1
next(70)  -> 2
next(60)  -> 1
next(75)  -> 4
next(85)  -> 6

For 75, the previous prices 60, 70, 60 are all <= 75 (and 80 is not), so the span is 4 counting today.

Brute force: scan backwards on every call

Store all prices in an ArrayList<Integer>. For each new price, walk back through the history while the earlier prices are <= today's, counting the days. A steadily rising sequence makes every call scan the whole history.

import java.util.ArrayList;
import java.util.List;

class StockSpanner {
    private final List<Integer> prices = new ArrayList<>();

    public int next(int price) {
        prices.add(price);
        int span = 0;
        for (int i = prices.size() - 1; i >= 0 && prices.get(i) <= price; i--) {
            span++;
        }
        return span;
    }
}

public class Main {
    public static void main(String[] args) {
        StockSpanner s = new StockSpanner();
        List<Integer> out = new ArrayList<>();
        for (int p : new int[]{100, 80, 60, 70, 60, 75, 85}) {
            out.add(s.next(p));
        }
        System.out.println(out);
    }
}

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

prices.get(i) <= price unboxes the Integer and compares int values. Time: O(n) per call, O(n^2) for n calls. Space: O(n).

Optimal: monotonic stack of (price, span)

Once a price is followed by a larger-or-equal one, its individual value no longer matters: any later span that reaches it can jump over its whole span in one step. So keep a stack of {price, span} pairs, stored as two-element int[] arrays in an ArrayDeque, with strictly decreasing prices. For a new price, start with span 1 and pop every entry whose price is <= the new one, adding their spans. Then push {price, span}.

Trace for 100, 80, 60, 70, 60, 75, 85:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class StockSpanner {
    private final Deque<int[]> stack = new ArrayDeque<>(); // each entry is {price, span}

    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{price, span});
        return span;
    }
}

public class Main {
    public static void main(String[] args) {
        StockSpanner s = new StockSpanner();
        List<Integer> out = new ArrayList<>();
        for (int p : new int[]{100, 80, 60, 70, 60, 75, 85}) {
            out.add(s.next(p));
        }
        System.out.println(out);
    }
}

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

Time: next is amortized O(1): each price is pushed once and popped at most once. Space: O(n) in the worst case (strictly decreasing prices).