Last Updated on October 13, 2022 by Sumit Kumar
What is Stock Span Problem:
Stock span problem is a commercial problem where we have a series of N prices on the daily basis. And you need to calculate the span of the stock’s price for all N days.
The stock’s price (Si) of the given day (i) is defined as the maximum number of successive days before the given day, for which the given price of the stock on the present day is lower than its price on the given day.
Stock Span 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]
Stock Span Problem 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 an 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.