Stock Span

version.cpp

// C++ program for a linear time solution for stock 
// span problem without using stack 
#include <iostream> 
#include <stack> 
using namespace std; 

// An efficient method to calculate stock span values 
// implementing the same idea without using stack 
void calculateSpan(int A[], int n, int ans[]) 
{ 
	// Span value of first element is always 1 
	ans[0] = 1; 

	// Calculate span values for rest of the elements 
	for (int i = 1; i < n; i++) { 
		int counter = 1; 
		while ((i - counter) >= 0 && A[i] >= A[i - counter]) { 
			counter += ans[i - counter]; 
		} 
		ans[i] = counter; 
	} 
} 

// A utility function to print elements of array 
void printArray(int arr[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 
} 

// Driver program to test above function 
int main() 
{ 
	int price[] = { 10, 4, 5, 90, 120, 80 }; 
	int n = sizeof(price) / sizeof(price[0]); 
	int S[n]; 

	// Fill the span values in array S[] 
	calculateSpan(price, n, S); 

	// print the calculated span values 
	printArray(S, n); 

	return 0; 
} 

version.py

# Python linear time solution for stock span problem 

# A stack based efficient method to calculate s 
def calculateSpan(price, S): 
	
	n = len(price) 
	# Create a stack and push index of fist element to it 
	st = [] 
	st.append(0) 

	# Span value of first element is always 1 
	S[0] = 1

	# Calculate span values for rest of the elements 
	for i in range(1, n): 
		
		# Pop elements from stack whlie stack is not 
		# empty and top of stack is smaller than price[i] 
		while( len(st) > 0 and price[st[-1]] <= price[i]): 
			st.pop() 

		# If stack becomes empty, then price[i] is greater 
		# than all elements on left of it, i.e. price[0], 
		# price[1], ..price[i-1]. Else the price[i] is 
		# greater than elements after top of stack 
		S[i] = i + 1 if len(st) <= 0 else (i - st[-1]) 

		# Push this element to stack 
		st.append(i) 


# A utility function to print elements of array 
def printArray(arr, n): 
	for i in range(0, n): 
		print (arr[i], end =" ") 


# Driver program to test above function 
price = [10, 4, 5, 90, 120, 80] 
S = [0 for i in range(len(price)+1)] 

# Fill the span values in array S[] 
calculateSpan(price, S) 

# Print the calculated span values 
printArray(S, len(price)) 

We see that S[i] on day i can be easily computed if we know the closest day preceding i, such that the price is greater than on that day than the price on day i. If such a day exists, let’s call it h(i), otherwise, we define h(i) = -1.
The span is now computed as S[i] = i – h(i). See the diagram.

To implement this logic, we use a stack as an abstract data type to store the days i, h(i), h(h(i)) and so on. When we go from day i-1 to i, we pop the days when the price of the stock was less than or equal to price[i] and then push the value of day i back into the stack.
O(n). It seems more than O(n) at first look. If we take a closer look, we can observe that every element of array is added and removed from stack at most once. So there are total 2n operations at most. Assuming that a stack operation takes O(1) time, we can say that the time complexity is O(n).