The Stock Span Problem

Difficulty Level Medium
Frequently asked in Amazon Delhivery MAQ
StackViews 3267

This problem “The Stock Span Problem” comes under the financial aspect. In this problem, we find the stock span for the stock price of each day. The maximum number of consecutive days just before any particular day for which the price of the stock of the days before it is less than or equal to its price of the stock is known as it’s span.

The Stock Span Problem

As in the above image of the stock span problem –

for day 1, stock price 100 – there is no smaller stock price of consecutive previous days, therefore, span = 1

day 2, stock price 80 – no smaller stock price of consecutive previous days, therefore, span = 1

day 3, stock price 60 – no smaller stock price of consecutive previous days, therefore, span = 1

day 4, stock price 70 – day 3 has smaller stock price i.e 60 therefore, span = 2

day 5, stock price 60 – no smaller stock price of consecutive previous days, therefore, span = 1

day 6, stock price 75 – day 3, day 4, day5 has smaller stock prices i.e 60, 70, 60 respectively, therefore, span = 4

day 7, stock price 85 – day 2, day 3, day 4, day5 and day 6 has smaller stock prices i.e 80, 60, 70, 60, 75 respectively, therefore, span = 6

Example

Let’s see some examples of The Stock Span Problem for the understanding of input-output.

Input : price = {100, 80, 60, 70, 60, 75, 85}

Output : Span of 7 days : 1 1 1 2 1 4 6

Input : price = {10, 4, 5, 90, 120, 80}

Output : Span of 6 days : 1 1 2 4 5 1

Without Using Stack

Naive Method for The Stock Span Problem

Algorithm

  1. Initialize an array to store the stock price of n days.
  2. Create another array S of size n to store the span.
  3. Traverse from 1 to n-1 and set the value at the current index of S[ ] as 1. Initialize inner loop from outer loop -1 till 0 while the price at the outer loop’s index is greater than or equal to the price at the inner loop’s index and increment the current index of S[ ] at every step of the inner loop.
  4. Print the array S[ ].

C++ Program for The Stock Span Problem

#include <bits/stdc++.h> 
using namespace std;  
  
void calculateSpan(int price[], int n, int S[]){  
    S[0] = 1;  
  
    for(int i = 1; i < n; i++){  
        S[i] = 1; 
  
        for (int j = i - 1; (j >= 0) &&  
                (price[i] >= price[j]); j--)  
            S[i]++;  
    }  
}  
  
void display(int arr[], int n){
    cout<<"Span of "<<n<<" days : "; 
    for (int i = 0; i < n; i++)  
        cout << arr[i] << " ";  
}  
  
int main(){  
    
    int price[] = {100, 80, 60, 70, 60, 75, 85};  
    int n = sizeof(price) / sizeof(price[0]);  
    int S[n];  
  
    calculateSpan(price, n, S);  
  
    display(S, n);  
  
    return 0;  
}
Span of 7 days : 1 1 1 2 1 4 6

Java Program for The Stock Span Problem

Span of 7 days : 1 1 1 2 1 4 6

Complexity Analysis

Time Complexity: O(n*n) where n is the number of days for which stock prices are given.

Auxiliary Space: O(n) because we used space to store span for n stock prices.

Using Stack

Efficient Method for The Stock Span Problem

Algorithm

  1. Initialize an array to store the stock price of n days.
  2. Create another array S of size n to store the span and a stack st of integer type.
  3. Traverse from 1 to n-1, while the stack is not empty and price of current index is greater than or equal to the price at the index equal to the value at top of stack, pop the top.
  4. Update the current index of S[ ] as current index + 1 is stack is an empty else current index – top of the stack and push/insert the current index in the stack.
  5. After the loop print the array S[ ].

C++ Program for The Stock Span Problem

#include <bits/stdc++.h> 
using namespace std;  
  
void calSpan(int price[], int n, int S[]){  
    
    stack<int> st; 
    st.push(0); 
  
    S[0] = 1; 
  
    for(int i = 1; i < n; i++){ 
        while ((!st.empty()) && (price[st.top()] <= price[i])){ 
            st.pop(); 
        }
  
        S[i] = (st.empty()) ? (i + 1) : (i - st.top()); 
  
        st.push(i); 
    }   
}  
  
void display(int arr[], int n){
    cout<<"Span of "<<n<<" days : "; 
    for (int i = 0; i < n; i++)  
        cout << arr[i] << " ";  
}  
  
int main(){  
    
    int price[] = {100, 80, 60, 70, 60, 75, 80 };  
    int n = sizeof(price) / sizeof(price[0]);  
    int S[n];  
  
    calSpan(price, n, S);  
  
    display(S, n);  
  
    return 0;  
}
Span of 7 days : 1 1 1 2 1 4 6

Java Program for The Stock Span Problem

import java.util.Arrays; 
import java.util.Stack; 
  
class spanStock{ 
    
    static void calSpan(int price[], int n, int S[]){ 
        
        Stack<Integer> st = new Stack<>(); 
        st.push(0); 
  
        S[0] = 1; 
  
        for(int i = 1; i < n; i++){ 
  
            while((!st.empty()) && (price[st.peek()] <= price[i])){ 
                st.pop(); 
            }
  
            S[i] = (st.empty()) ? (i + 1) : (i - st.peek()); 
  
            st.push(i); 
        }  
    } 
  
    static void display(int arr[]){ 
        System.out.print("Span of "+arr.length+" days : "); 
        for (int i = 0; i < arr.length; i++)  
            System.out.print(arr[i]+" ");  
    } 
  
    public static void main(String[] args){ 
        
        int price[] = {100, 80, 60, 70, 60, 75, 85}; 
        int n = price.length; 
        int S[] = new int[n]; 
  
        calSpan(price, n, S); 
  
        display(S); 
    } 
}
Span of 7 days : 1 1 1 2 1 4 6

Complexity Analysis

Time Complexity: O(n) where n is the number of days for which stock prices are given.

Auxiliary Space: O(n) because we used space to store span for n stock prices.

References

Translate »