The Stock Span Problem

Problem statement

Given the daily price of a stock for n days, find the stock’s span of the n days. Stock span of the stock’s price of the current day is defined as the maximum number of days (starting today and going backwards) for which the stock price was less than or equal to the price of the current day.

Input: Integer array of size of n.
Output: Integer array of size n.

Test cases:
Input:
[90, 40, 20, 30, 80, 60, 100]

Output:
[1, 1, 1, 2, 4, 1, 7]

Explanation:

  • Span for price 90 will be 1 as there is no price to its left.
  • Span for price 40 will be 1 as there is no smaller price to its left.
  • Span for price 20 will be 1 as there is no smaller price to its left.
  • Span for price 30 will be 2 as there is 1 smaller price to its left i.e, 20.
  • Span for price 80 will be 4 as there are 3 smaller prices to its left i.e, 40, 20, 30.
  • Span for price 60 will be 1 as there is no smaller price to its left.
  • Span for price 100 will be 7 as there are 6 smaller prices to its left i.e, 90, 40, 20, 30, 80, 60.

Naive Approach – Brute Force

The idea is to simply traverse the price array and for each price we will count the number of prices smaller than or equal to the current price on its left side using a nested loop.

Algorithm

1. Traverse the price array
2. For each i in 0 to n:
    a. Iterate j, while there are elements to the left and the 
    b. price[j] is less than the current price.
        i. Increment count and decrement j.
    c.Set span[i] as count.
3. Return span array.

Code Implementation:


import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
    // Function to find the stock span
    public static int[] getStockSpan(int price[], int n){
        int span[] = new int[n];

        // Traverse the price array
        for(int i = 0; i < n; i++){
            int count = 0;
            int j = i;
            
            // Iterate while there are element to the left and the price is less than the current price
            while(j >= 0 && price[j] <= price[i]){
                count++;
                j--;
            }
            span[i] = count;
        }
        
        // Return the span array
        return span;
    }
	public static void main(String[] args) {
		int price[] = new int[]{90, 40, 20, 30, 80, 60, 100};
		int span[] = getStockSpan(price, price.length);
		for(int s : span){
		    System.out.print(s + " ");
		}
	}
}

Output:

1 1 1 2 4 1 7

Time complexity: O(n^2). It takes O(n) to find the stock span of one day, and we have to find the span for n days. Hence, the time complexity will be O(n^2)

Space Complexity: O(n). The space required is only for the input and output array. The auxiliary space complexity is O(1).

Efficient Approach – Using Stack

The stock span problem can be solved efficiently using stack data structure. The idea is to use a stack to maintain the prices in monotonically decreasing order. We will iterate over the price array and for each price we will find the price just greater than the current price, lying on the left side of the array.

To do this we will check the top of the stack and if the price[top] is less than or equal to the current price we will pop the top element of the stack. We will keep doing this until we don’t find a price greater than the current price or the stack becomes empty.

Case 1: The stack becomes empty. If the stack becomes empty, it will mean that there is no price greater than the current price to the left and so the span will be (current index + 1). Plus 1 because we are using 0-based indexing.

Case 2: We find a price greater than the current price. Then the span will be (current index – index of the greater price).

Algorithm

1. Initialize an empty stack. This stack will be used to store the indexes.
2. Add index of first price to the stack.
3. Set 'span[0]' as 1 because there is no price to its left.
4. Iterate i from 0 to n. 
    a. Find the next greater price of the price[i] to the left. 
    b. While stack is not empty and price[st.peek()] <= price[i]
        i. st.pop()
    c. Now if stack is empty, set span[i] = i + 1
    d. Otherwise, span[i] = i - st.peek()
5. Return span array.

Code Implementation:


import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
    public static int[] getStockSpan(int price[], int n){
        
        // Initialize an empty stack.
        // This stack will be used to store the indexes.
        Stack<Integer> st = new Stack<>();
        
        // 'span' array will store the final answer.
        int span[] = new int[n];
        
        // Add index of first price to the stack.
        st.push(0);
        
        // Set 'span[0]' as 1 because there is no price to its left.
        span[0] = 1;
        
        // Iterate over the `price` array to find the span of each price.
        for(int i = 1;i<n;i++){
            
            // Find the next greater price to the left. 
            while(!st.isEmpty() && price[st.peek()] <= price[i]){
                st.pop();
            }
            
            // Case 1: If there is no greater price to the left, it means the current price is the greatest so far.
            if(st.isEmpty()){
                span[i] = i + 1;
            }
            
            // Case 2: Else find the number of consecutive days from the current day to the day which has the next greater price.
            else{
                span[i] = i - st.peek();
            }
            
            // Push the index of the current price to the stack.
            st.push(i);
        }
        
        // Return the span array.
        return span;
    }

	public static void main(String[] args) {
		int price[] = new int[]{90, 40, 20, 30, 80, 60, 100};
		int span[] = getStockSpan(price, price.length);
		for(int s : span){
		    System.out.print(s+" ");
		}
	}
}

Output:

1 1 1 2 4 1 7

Time complexity: O(n). We can observe that every element is pushed and removed from the stack only once. Hence, the total operations being performed is 2n and O(2n) = O(n) because we don’t consider constant terms during asymptotic analysis of time complexity.

Space Complexity: O(n). O(n) space is required for the input and output array. The auxiliary space complexity is also O(n) as we are using a stack. At any point of time the stack can contain at most n elements.

This article tried to discuss the most efficient way to solve the Stock Span Problem. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.

Leave a Reply

Your email address will not be published. Required fields are marked *