## 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**

- If the stack is not
- 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).