# Stock Span Problem

## Problem Statement

Given a list of prices of a stock for N days. The task is to find the stack span for each day.
Stock span can be defined as the number of consecutive days before the current day where the price of the stack was equal to or less than the current price.

Examples:

Input: A[] = [100,60,70,65,80,85]
Output: [1,1,2,1,4,5]
Explanation: Explained in image above.

Input: [31, 27, 14, 21, 30, 22]
Output: [1, 1, 1, 2, 4, 1]

## Brute Force Approach

A simple approach to solve this problem is to run two nested loops and for each element, find the maximum length such that all consecutive elements are smaller than the current element.
In case a large element is found, terminate the loop.

### C++ Code

```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]++;
}
}```

### Java Code

```static 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]++;
}
}```

### Python Code

```def calculateSpan(price, n, S):
S[0] = 1
for i in range(1, n, 1):
S[i] = 1
j = i - 1
while (j>= 0) and (price[i] >= price[j]) :
S[i] += 1
j -= 1```

Time Complexity:O(N^2), where N is total size of the array
Space Complexity:O(1), as no extra space is used

## Approach 2: Stack

Instead of traversing through all previous elements of the current element, we can use the Stack data structure which can solve the problem in linear time.
The approach of this problem is very similar to Next Greater Element. But, the indices of the next greater element is stored instead of the element itself.

Algorithm

• Initialise an array S[0] = 1 for day 0.
• Initialise a stack and push the index of the first day into the stack.
• Traverse a loop from 1 to N and for each iteration, do the following:
• If the stack is not empty and price of current element is greater than the top of stack, pop the element.
• Else if, stack is not empty then, subtract index from S[i], i.e. S[i] = i – S.top().
• Else, S[i] =  i + 1
• Push the current index i into the stack.

### C++ Implementation

```void calculateSpan(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);
}
}```

### Java Implementation

```static void calculateSpan(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);
}
}```

### Python Implementation

```def calculateSpan(price, S):

n = len(price)
st = []
st.append(0)

S[0] = 1

for i in range(1, n):
while( len(st) > 0 and price[st[-1]] <= price[i]):
st.pop()

S[i] = i + 1 if len(st) <= 0 else (i - st[-1])

st.append(i)```

Time Complexity:O(N), where N is total size of the array
Space Complexity:O(1), as no extra space is used.

Practice Questions

Best time to buy and sell stocks

## FAQs

What is Stock Span Problem?
Stock span
can be defined as the number of consecutive days before the current day where the price of the stack was equal to or less than the current price.

What is the most efficient approach to solving the stock span problem?
The stack-based approach is the most efficient approach to solve the problem. The time complexity is O(N) and space complexity is O(1).