Backward Price Span for Each Trading Day
Solve this Problemprices, find, for every day, how many consecutive days — counting today, and walking backward — the price has stayed at or below today's price before a strictly higher price finally breaks the streak.
This is a "previous greater element" problem wearing a counting hat: instead of the value of the nearest strictly-higher day to the left, you want the distance to it. A monotonic decreasing stack of day indices tracks exactly that: whenever a new day's price is high enough to pop earlier days off (because it's at or above them), those days can never again bound anyone's span, since a higher wall now stands between them and the future. Once popping stops, whatever remains on top is the closest day still strictly higher — the boundary — and the span is simply the index gap to it (or all the way back to day 0, if the stack empties completely).
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ prices.length ≤ 15 - ◆
1 ≤ prices[i] ≤ 1000
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Walk Backward From Each Day
BruteFor every day i, walk backward one day at a time, extending the span by 1 for as long as the price stays at or below today's price, and stopping the moment a strictly higher price is found (or the start of the record is reached). This checks the full backward run for every day directly — O(n) per day, O(n²) overall.
O(n²)O(1)1class Solution {
2 public int[] stockSpan(int[] prices) {
3 int n = prices.length;
4 int[] result = new int[n];
5 for (int i = 0; i < n; i++) {
6 int span = 1;
7 for (int j = i - 1; j >= 0; j--) {
8 if (prices[j] <= prices[i]) {
9 span++;
10 } else {
11 break;
12 }
13 }
14 result[i] = span;
15 }
16 return result;
17 }
18}Optimal — Monotonic Decreasing Stack of Day Indices
OptimalKeep a stack of day indices whose prices are strictly decreasing from bottom to top. For each new day, pop off every day whose price is at or below today's — they can never bound anyone's span again once a day at least as high as them has appeared. The day now on top (if any) is the closest day with a strictly higher price, so today's span is just the gap between the current index and that one (or i+1 if the stack empties completely, meaning the span reaches all the way back to the start). Push the current day and move on — each day is pushed once and popped at most once, giving O(n) total work.
O(n)O(n)1class Solution {
2 public int[] stockSpan(int[] prices) {
3 int n = prices.length;
4 int[] result = new int[n];
5 Deque<Integer> stack = new ArrayDeque<>();
6 for (int i = 0; i < n; i++) {
7 while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
8 stack.pop();
9 }
10 result[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
11 stack.push(i);
12 }
13 return result;
14 }
15}