Stock Span Problem – LeetCode Solution [Medium]

The stock span problem is a financial problem 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 today’s price.

For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}

Problem

GeeksforGeeks Problem Link

Pseudocode

1. Create an array S[n] (Stock Span array) and store S[0] = 1 (Since there are no preceding days). Also initialize a stack st. And push 0 int stack – Push(st, 0).
2. Traverse stock array arr[n].
3. While arr[i] >= st.top() 
     st.pop()
ie get the farthest consecutive 'j' for which current arr[i] > arr[j] [or st.top()]
4. S[i] = i - st.top() [j]
5. st.push(i)
6. Array S[n] is the required Stock Span

Time Complexity: O(n)
Space Complexity/Auxiliary Space: O(n) (n: size of stack)

Code Implementation

//
//  main.cpp
//  Stock Span
//
//  Created by Himanshu on 11/09/21.
//

#include <iostream>
#include <stack>
using namespace std;

void printArray (int arr[], int n) {
    for (int i=0; i<n; i++) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

void solve(int S[], int arr[], int n) {
    stack<int> st;
    
    S[0] = 1;
    st.push(0);
    
    for (int i=1; i<n; i++) {
        
        while (!st.empty() && arr[st.top()] < arr[i]) {
            st.pop();
        }
        
        if (st.empty()) {
            S[i] = i + 1;
        } else {
            S[i] = i - st.top();
        }
        
        st.push(i);
    }
}

int main () {
    int n = 7;
    int arr[] = {100, 80, 60, 70, 60, 75, 85};
    int S[n];
    
    cout<<"Initial array:"<<endl;
    printArray(arr, n);

    solve (S, arr, n);
    
    cout<<"Stock Span:"<<endl;
    printArray(S, n);

    return 0;
}

Output

Initail array:
100 80 60 70 60 75 85 
Stock Span:
1 1 1 2 1 4 6 

Here’s a working example: Ideone

Practice problem

Stock Span problem [LeetCode]