## Problem Statement

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 span of stock’s price for all n days.

The span `S[i]` of the stock’s price on a given day `i` is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to its price on day `i`.

For example, if the price of a stock over a period of 7 days are [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Explanation

``````Stock price    Max Consecutive days (starting from today) for which the stock price was
less than or equal to the current price

100            1
80             1
60             1
70             2
60             1
75             4
85             6``````

## Solution

### Brute Force

``````import java.util.Scanner;
import java.util.Stack;

class StockSpanProblem {
private static int[] stockSpan(int[] stockPrices) {
int n = stockPrices.length;
int[] span = new int[n];

for(int i = 0; i < n; i++) {
span[i] = 1;
for(int j = i-1; j >= 0; j--) {
if(stockPrices[j] <= stockPrices[i]) {
span[i]++;
} else {
break;
}
}
}

return span;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] stockPrices = new int[n];
for (int i = 0; i < n; i ++) {
stockPrices[i] = keyboard.nextInt();
}
keyboard.close();

int[] span = stockSpan(stockPrices);
for(int i = 0; i < n; i++) {
System.out.print(span[i] + " ");
}
System.out.println();
}
}``````

Time Complexity: `O(n^2)` Space Complexity: `O(1)`

### Using Stack

``````import java.util.Scanner;
import java.util.Stack;

class StockSpanProblem {
private static int[] findNearestGreaterToLeftUsingStack(int[] stockPrices) {
int n = stockPrices.length;
int[] NGL = new int[n];
Stack<Integer> s = new Stack<>();

for(int i = 0; i < n; i++) {
NGL[i] = -1;
while(!s.empty()) {
int top = s.peek();
if(stockPrices[top] > stockPrices[i]) {
NGL[i] = top;
}
}
s.push(i);
}

return NGL;
}

private static int[] stockSpanUsingStack(int[] stockPrices) {
int[] NGL = findNearestGreaterToLeftUsingStack(stockPrices);
int[] span = new int[NGL.length];
for(int i = 0; i < NGL.length; i++) {
span[i] = i - NGL[i];
}
return span;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] stockPrices = new int[n];
for (int i = 0; i < n; i ++) {
stockPrices[i] = keyboard.nextInt();
}
keyboard.close();

int[] span = stockSpan(stockPrices);
for(int i = 0; i < n; i++) {
System.out.print(span[i] + " ");
}
System.out.println();
}
}``````

Time Complexity: `O(n)`, The entire array (of size n) is scanned only once. Each of the stack’s n elements are pushed and popped exactly once.

Space Complexity: `O(n)`