Problem

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate the span of the stock’s price for all n days.

The span S[i] of the stock’s price on a given day i is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to its price on day i.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: prices = [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
Explanation: For each day, the span is calculated as follows:
Price        Span      Reason
100            1       (No previous day)
80             1       (No previous day <= 80)
60             1       (No previous day <= 60)
70             2       (Day 2 and 3 itself)
60             1       (No previous day <= 60)
75             4       (Days 3, 2, 1, and 0)
85             6       (Days 5, 4, 3, 2, 1, and 0)

Example 2:

1
2
3
4
5
6
7
8
9

Input: prices = [10, 4, 5, 90, 120, 80]
Output: [1, 1, 2, 4, 5, 1]
Explanation: For each day, the span is calculated as follows:
- Day 0: Price = 10, Span = 1 
- Day 1: Price = 4, Span = 1
- Day 2: Price = 5, Span = 2
- Day 3: Price = 90, Span = 4
- Day 4: Price = 120, Span = 5
- Day 5: Price = 80, Span = 1

Solution

Method 1 - Brute Force

We can run the 2 nested loops - In outer loop iterate through the prices array, and in inner loop:

  • For each price prices[i], we initiate span[i] as 1 (the minimum span value, i.e., the current day itself).
  • We then use an inner loop to check all previous prices prices[j] from i-1 down to 0.
  • If a previous price prices[j] is less than or equal to the current price prices[i], we increment span[i].
  • If we encounter a price greater than prices[i], we break out of the inner loop as the span cannot be extended further.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int[] calculateSpan(int[] prices) {
        int n = prices.length;
        int[] span = new int[n];

        for (int i = 0; i < n; i++) {
            span[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (prices[j] <= prices[i]) {
                    span[i]++;
                } else {
                    break;
                }
            }
        }

        return span;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def calculateSpan(self, prices: List[int]) -> List[int]:
        n = len(prices)
        span = [0] * n

        for i in range(n):
            span[i] = 1
            for j in range(i - 1, -1, -1):
                if prices[j] <= prices[i]:
                    span[i] += 1
                else:
                    break

        return span

Complexity

  • ⏰ Time complexity: O(n^2) due to the nested loops.
  • 🧺 Space complexity: O(n) for the output array

Method 2 - Using Monotonic decreasing Stack

To solve the stock span problem efficiently, we can use a monotonic decreasing stack to store the indices of the days. For each day i, we pop elements from the stack until we find a day with a price greater than the price of the current day. The span for the current day will then be the difference in indices. So,

1

span[i] = i - ngl(i) if ngl(i) exists otherwise -1

where NGL is nearest greater element on the left of current element. if it exists.

Here is the approach:

  1. Initialize a stack to keep the indices of the days.
  2. Initialize an array to store the span values.
  3. Iterate through the price list:
    • For each price, pop elements from the stack until the top of the stack has a price greater than the current price.
    • If the stack is empty, it means all previous prices are less than the current price’s price.
    • Update the span for the current day.
    • Push the current index onto the stack.
  4. Return the span array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public int[] calculateSpan(int[] prices) {
        int n = prices.length;
        int[] span = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
                stack.pop();
            }
            span[i] = (stack.isEmpty()) ? (i + 1) : (i - stack.peek());
            stack.push(i);
        }
        
        return span;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] prices1 = {100, 80, 60, 70, 60, 75, 85};
        int[] span1 = sol.calculateSpan(prices1);
        
        for (int sp : span1) {
            System.out.print(sp + " ");
        }
        System.out.println();
        
        int[] prices2 = {10, 4, 5, 90, 120, 80};
        int[] span2 = sol.calculateSpan(prices2);
        
        for (int sp : span2) {
            System.out.print(sp + " ");
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def calculateSpan(self, prices: List[int]) -> List[int]:
        n = len(prices)
        span = [0] * n
        stack = []
        
        for i in range(n):
            while stack and prices[stack[-1]] <= prices[i]:
                stack.pop()
            span[i] = i + 1 if not stack else i - stack[-1]
            stack.append(i)
        
        return span

# Example usage
sol = Solution()
prices1 = [100, 80, 60, 70, 60, 75, 85]
span1 = sol.calculateSpan(prices1)
print(span1)  # Output: [1, 1, 1, 2, 1, 4, 6]

prices2 = [10, 4, 5, 90, 120, 80]
span2 = sol.calculateSpan(prices2)
print(span2)  # Output: [1, 1, 2, 4, 5, 1]

Complexity

  • ⏰ Time complexity: O(n) as each element is pushed and popped from the stack at most once.
  • 🧺 Space complexity: O(n) for space required for the stack and the resulting span array.

Method 3 - Using NGL solution

This boils down to NGL - Nearest Greater Element to Left of every element

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.Scanner;
import java.util.Stack;

class Solution {

    private int[] stockSpanUsingStack(int[] stockPrices) {
        int[] NGL = findNearestGreaterToLeftUsingStack(stockPrices);
        int[] span = new int[NGL.length];
        for(int i = 0; i < NGL.length; i++) {
            span[i] = i - NGL[i];
        }
        return span;
    }

}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)