Stock Span Problem Solution – LeetCode

The stock span problem (Leetcode) 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 (arr) 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 statement

https://www.geeksforgeeks.org/the-stock-span-problem/

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 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;
}

Here’s a working example:

https://ideone.com/YsWUc0

Practice problem

  1. https://leetcode.com/problems/online-stock-span/ [Stock span problem Leetcode]

Leave a Reply

Your email address will not be published.