The Stock Span Problem

4 min readJan 14, 2021

What is a stock span?

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate the span of stock’s price for all n days. Given a list of rates of a certain stock for some number of days, the stock span is the number of consecutive days (before a specific day) when the price of the stock was less than or equal to the price on this specific day.

For e.g. — {100, 80, 60, 70, 60, 75, 85}. This is an array of 7 days prices and the span value for these 7 days is {1, 1, 1, 2, 1, 4, 6}.

Now the question arises, how this span is calculated?

This is very simple.

· The span of the first element (100) is always 1 (including that element i.e. 100) because there is no other element before this.

· The span of the second element (80) is 1 because before 80 there is one element i.e. 100 and it is greater than 80.

· The span of the third element (60) is also 1 because 80 and 100, are greater than 60.

· The span of the fourth element (70) is 2 as when we traverse back there is only 1 element just before 70 i.e. 60, which is less than 70 and the second element is 70 itself.

· For the fifth element, the span is 1 because the just prior element (70) is greater than 60, so we don’t traverse further.

· For the sixth element, it is 4 because consecutive 3 elements (60, 70, 60) are less than 75 and the fourth element is 75 itself.

· The span for the last element (85) is 6 as five adjacent elements (75, 60, 70, 60, 80) are less than 85, plus one is for 85 itself.

Got the theory well, but what about the code? How to implement it?

So, there are two ways to implement the stock span in c++.

A simple but inefficient method.

// Brute force method

#include <bits/stdc++.h>

using namespace std;

// Fills array S[] with span values

void calculateSpan(int price[], int n, int S[])

{ // Span value of first day is always 1 as explained above.

S[0] = 1;

// Calculate span value of remaining days by linearly checking previous days

for (int i = 1; i < n; i++) //n is the size of prize array.

{ S[i] = 1; // Initialize span value

// Traverse left while the next element on left is smaller than and equal to price[i].

for (int j = i — 1; (j >= 0) && (price[i] >= price[j]); j — )

S[i]++; // Increasing the span value for that price element.

}

void printArray(int span[], int n)

{

for (int i = 0; i < n; i++)

cout << span[i] << “ “;

}

int main()

{

int price[] = { 10, 4, 5, 90, 120, 80 };

int n = sizeof(price) / sizeof(price[0]);

int S[n];

calculateSpan(price, n, S);

printArray(S, n); // OUTPUT : 1 1 2 4 5 1

return 0;

}

The Time Complexity of the above method is O(n²).

A Linear time complexity method

#include <iostream>

#include <stack>

using namespace std;

// A stack based efficient method to calculate.

void calculateSpan(int price[], int n, int S[])

{ // Create a stack and push index of first element to it

stack<int> st;

st.push(0); // index of first element.

S[0] = 1; // Span value of first element is always 1.

// Calculate span values for rest of the elements

for (int i = 1; i < n; i++) {

// Pop elements from stack while stack is not empty and top of stack is smaller than price[i]

while (!st.empty() && price[st.top()] <= price[i])

st.pop();

// If stack becomes empty, then price[i] is greater than all elements on left of it. Else price[i] is greater than elements after top of stack.

S[i] = (st.empty()) ? (i + 1) : (i — st.top());

st.push(i); //Push the index of the element you checked.

}