Stock span problem

Hard

Jump back to the previous greater price

Problem

For each day, the span is the number of consecutive prior days (including today) with price <= today's price. Return the spans.

In simple words

Use a stack to jump back to the last higher price; the gap is today's span.

The idea

The span ends at the first earlier day with a strictly greater price, so a decreasing monotonic stack of indices finds it directly. Popping smaller prices is safe because they can never bound a later span.

The trick

Span = current index - index of previous greater price.
An empty stack means every earlier price was smaller: the span is the whole prefix.
Amortised O(1) per day.

←→stepspaceplay

100

1/9

Brute force

timeO(n²)spaceO(1)

Walk back each day.

1for (let i = 0; i < n; i++) {2  let span = 1;3  for (let j = i - 1; j >= 0 && prices[j] <= prices[i]; j--) span++;4  res[i] = span;5}

Input

array: [100, 80, 60, 70, 60, 75, 85]

Output

spans: —
answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: prices = [100, 80, 60, 70, 60, 75, 85]
Output:: [1, 1, 1, 2, 1, 4, 6]
Explanation:: Span = consecutive days with price <= today.

Example 2

Input:: prices = [10, 4, 5, 90, 120, 80]
Output:: [1, 1, 2, 4, 5, 1]
Explanation:: 90 and 120 have long rising spans.

Example 3

Input:: prices = [1, 2, 3]
Output:: [1, 2, 3]
Explanation:: Each day beats all before → 1,2,3.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.