## Definition

Stock Span Problem comes under economical aspects where we have a series of the stock price quoted for a stock every day and involves calculating the span of the stock price for all number of days, the maximal number of days for which the stock price is equal to or less than the present days. In other words, it involves finding the number of days to the first day, where the stock price of the present day is higher than that of the current day. This problem is used to determine the sentiment of the market.

### Introduction to Stock Span Problem

The stock span problem is solved by using the data structures as it provides an effective and efficient way to track the maximum number of days that were successive for which the stock price was equal to or less than to given price. This is a classic problem in finance which involves determining whether the stock price is lower than the current day stock price. The goal of the stock span problem is to find the maximum no. of consecutive days, which is helpful in analyzing the trends of stock price.

This problem is approached by using the data structures as it provides an efficient way to track the stock price. This is an essential financial concept and is widely used in the stock market for decision-making, analysis, and investment. To understand the solution and problem of the stock span, investors make the decisions to take advantage of market trends to maximize the returns of their stock.

### Naive Approach – Brute Force

The naïve approach uses brute force to find the span of every stock price. This is done iteratively after counting the number of elements from the left to the right side of the current element that was equal to or greater than the current element. Below is the algorithm of naïve brute force algorithm as follows.

**Algorithm:**

- Start
- Traverse the price array.
- Run for loop for each i into the 0 to n.
- Iterate the j elements when there is the element to the right-hand side.
- If price j is less than the current price, then increment the count and need to decrement the j.
- Then set the span[i] as count.

- Then return the array of spans.
- Stop

Below are the programs of the naïve approach.

##### C Language

**Code:**

```
#include <stdio.h>
void calspan(int pr[], int n, int S[])
{
S[0] = 1;
for (int a = 1; a < n; a++) {
S[a] = 1;
for (int b = a - 1;
(b >= 0) && (pr[a] >= pr[b]); b--)
S[a]++;
}
}
void printArray (int arr[], int n)
{
for (int a = 0; a < n; a++)
printf ("%d ", arr[a]);
}
int main()
{
int pr[] = { 13, 7, 6, 80, 150, 70 };
int n = sizeof(pr) / sizeof(pr[0]);
int S[n];
calspan(pr, n, S);
printArray(S, n);
return 0;
}
```

**Output:**

Time complexity – O(N^2)

Auxiliary space – O(N)

##### C++ Language

**Code:**

```
#include <bits/stdc++.h>
using namespace std;
void calsp (int pr[], int n, int S[])
{
S[0] = 1;
for (int a = 1; a < n; a++) {
S[a] = 1;
for (int b = a - 1;
(b >= 0) && (pr[a] >= pr[b]); b--)
S[a]++;
}
}
void par(int arr[], int n)
{
for (int a = 0; a < n; a++)
cout << arr[a] << " ";
}
int main()
{
int pr[] = { 13, 7, 6, 80, 150, 70 };
int n = sizeof(pr) / sizeof(pr[0]);
int S[n];
calsp(pr, n, S);
par(S, n);
return 0;
}
```

**Output:**

Time complexity – O(N^2)

Auxiliary space – O(N)

##### Python Language

**Code:**

```
def calsp(pr, n, S):
S[0] = 1
for a in range(1, n, 1):
S[a] = 1
b = a - 1
while (b >= 0) and (pr[a] >= pr[b]):
S[a] += 1
b -= 1
def par(arr, n):
for a in range(n):
print(arr[a], end=" ")
pr = [ 13, 7, 6, 80, 150, 70 ]
n = len(pr)
S = [None] * n
calsp(pr, n, S)
par(S, n)
```

**Output:**

Time complexity – O(N^2)

Auxiliary space – O(N)

##### Java Language

**Code:**

```
import java.util.Arrays;
class naive
{
static void csp(int pr[], int n, int S[])
{
S[0] = 1;
for (int a = 1; a < n; a++) { S[a] = 1; for (int b = a - 1; (b >= 0) && (pr[a] >= pr[b]); b--)
S[a]++;
}
}
static void par(int arr[])
{
System.out.print (Arrays.toString(arr));
}
public static void main(String[] args)
{
int pr[] = { 13, 7, 6, 80, 150, 70 };
int n = pr.length;
int S[] = new int[n];
csp(pr, n, S);
par(S);
}
}
```

**Output:**

Time complexity – O(N^2)

Auxiliary space – O(N)

### Stock Span Problem using Stack

This problem will come with the financial aspect. The consecutive days of the greatest number are given in a stock price that is less than the present price. There are two methods of stock span problem i.e. efficient and inefficient methods. Below is the algorithm of the stock span problem as follows.

**Algorithm:**

- Start
- Initialize an empty stack.
- After initializing the stack, add the index in the first price of the stack.
- Then iterate the I from 0 to n.
- Then find the greater price of price [i]
- If the stack is not empty and the price is greater than the peak then pop the st.
- If stack is empty, set span[i] = i+1

- Then return span array.
- Stop

##### C++ Language

**Code:**

```
#include <bits/stdc++.h>
using namespace std;
void csp(int pr[], int n, int S[])
{
stack sta;
sta.push(0);
S[0] = 1;
for (int a = 1; a < n; a++) {
while (!sta.empty() && pr[sta.top()] <= pr[a])
sta.pop();
S[a] = (sta.empty()) ? (a + 1) : (a - sta.top());
sta.push(a);
}
}
void par(int arr[], int n)
{
for (int a = 0; a < n; a++)
cout << arr[a] << " ";
}
int main()
{
int pr[] = { 13, 7, 6, 80, 150, 70 };
int n = sizeof(pr) / sizeof(pr[0]);
int S[n];
csp(pr, n, S);
par(S, n);
return 0;
}
```

**Output:**

Time complexity – O(N)

Auxiliary space – O(N)

##### Java Language

**Code:**

```
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class stack {
static void cspan(int pr[], int n, int S[])
{
Deque sta = new ArrayDeque();
sta.push(0);
S[0] = 1;
for (int a = 1; a < n; a++) {
while (!sta.isEmpty()
&& pr[sta.peek()] <= pr[a])
sta.pop();
S[a] = (sta.isEmpty()) ? (a + 1)
: (a - sta.peek());
sta.push(a);
}
}
static void par(int arr[])
{
System.out.print(Arrays.toString(arr));
}
public static void main(String[] args)
{
int pr[] = { 10, 4, 5, 90, 120, 80 };
int n = pr.length;
int S[] = new int[n];
cspan(pr, n, S);
par(S);
}
}
```

**Output:**

Time complexity – O(N)

Auxiliary space – O(N)

##### Python Language

**Code:**

```
def cspan(price, S):
n = len(pr)
sta = []
sta.append(0)
S[0] = 1
for a in range(1, n):
while(len(sta) > 0 and pr[sta[-1]] <= pr[a]):
sta.pop()
S[a] = a + 1 if len(sta) == 0 else (a - sta[-1])
sta.append(a)
def par(arr, n):
for a in range(0, n):
print(arr[a], end=" ")
pr = [10, 4, 5, 90, 120, 80]
S = [0 for i in range(len(pr)+1)]
cspan(pr, S)
par(S, len(pr))
```

**Output:**

Time complexity – O(N)

Auxiliary space – O(N)

##### C Language

**Code:**

```
#include
#define MS 100
int stack[MS], top = -1;
void push(int x)
{
if (top == MS -1) {
printf("Stack OF\n");
exit(1);
}
stack[++top] = x;
}
int pop()
{
if (top == -1)
{
printf("stack UF");
exit(1);
}
return stack[top--];
}
int peek()
{
return stack[top];
}
int isEmpty()
{
return top == -1;
}
void stockspan(int pr[], int n, int sp[])
{
sp[0] = 1;
push(0);
for (int a = 1; a < n; a++) { while (!isEmpty() && pr[a] >= pr[peek()]) {
pop();
}
if (isEmpty()) {
sp[a] = a+1;
} else {
sp[a] = a - peek();
}
push(a);
}
}
int main()
{
int pr[] = { 10, 4, 5, 90, 120, 80 };
int n = sizeof(pr) / sizeof(pr[0]);
int sp[n];
stockspan(pr, n, sp);
for (int a = 0; a < n; a++) {
printf("%d", sp[a]);
}
return 0;
}
```

**Output:**

Time complexity – O(N)

Auxiliary space – O(N)

### Conclusion

The stock span problem is a coding challenge in which we have to find the span of the stock price for the specified day. This is defined as the maximum number of consecutive days before the given day for which the stock price is either lower than or equal to the present day. The stack of the solution decreases the span problem, and it will implement it using the data structure, linked list, and arrays.

### Recommended Article

We hope that this EDUCBA information on “Stock Span Problem” was beneficial to you. You can view EDUCBA’s recommended articles for more information,

360+ Online Courses | 1500+ Hours | Verifiable Certificates | Lifetime Access

4.7

View Course

Related Courses