## Stacks : Stock Span Problem

Tags: , , , ,

The Stock Span problem is commonly asked in Google and Amazon interviews and taught as the application of the stack data structure in universities. Let’s take a look at the problem statement:

Given a list of prices of a single stock for N number of days, find stock span for each day. Stock span is defined as a number of consecutive days prior to the current day when the price of a stock was less than or equal to the price at current day.

For example, {100,60,70,65,80,85} span will be {1,1,2,1,4,5}. If you are preparing for an interview, you can signup for a free session to find a coach to help you with your preparation.

For the first day, span is always 1. In the example we can see that for day 2 at 60, there is no day before it where the price was less than 60. Hence span is 1 again. For day 3, the price at day 2 (60) is less than 70, hence span is 2. Similarly, for day 4 and day 5. Remember days should be consecutive, that’s why the span for day 4 is 1 – even though there was a day 2 where the price was less than 65. Stock span problem is slightly complicated to understand but the solution is pretty easy.

Let’s look at the solution. Brute force solution would be: For each day, say current day, scan all days prior to it and increment span till the price of the stock is higher than current day. For the simple implementation, the time complexity is `O(n2)` where n is the number of days.

## Stock Span problem: Solution

If we observe the brute force algorithm, it is evident that we are interested in a day which has a stock price that is greater than the current day’s stock price. So, we need to check the last price which was greater than the current day’s price. Can you see a potential pattern? Which is the data structure which allows you to maintain the last price and see it first? What should be the invariant here? We should be using a stack for sure! The invariant is that the stack elements should be in the increasing order of price. The element at the top should be the maximum price seen till the current day. How can we maintain this?

Go through each day stock price, check if the current price on top of the stack is less than the current day’s price. If yes, pop out till price on top of the stack is greater than current day’s price, the stock span of the current day is the difference between the day of price on top of the stack and current day.
Storing the index of the last greatest stock price (i.e. the day when stock was of that price) would make things easier as compared to storing actual stock price on the stack. Hence, store the index `i` on the stack and `price[i]` will give us the price of the stock on the ith day.

### Stock Span Problem: Algorithm

1. Initialize span of day 1 (i=0) as 1 and put on to the stack.
2. For i=1 to n, do following
3. While `price[stack.top()] < price[i]` and !stack.isEmpty(), stack.pop()
4. If `price[stack.top()] > price[i]`, span = (i – stack.top())
5. Push current day index `i` on to stack.

Let’s take an example and see if this works? Let’s say prices are given on certain days are as following: 100, 60, 70, 65, 80, 85, 200

As per the above algorithm, we will put span = 1 and stack will be .
On day 2, stock price is 60. Stock price on day at the top of stack is 100, which is greater than 60. So `span` = 1- 0 = 1. Stack = [0,1]
On day 3, stock price is 70. We will pop from the stack till `price[stack.top()]` < 70, which obviously pops out 1 as price = 60. So `span` = 2 – 0 = 2. Push new price on stack, stack = [0,2]
On day 4, stock price is 65. `price[stack.top()]` > `price`, so `span` = 3-2=1. Stack = [0,2,3]
On day 5, stock price is 80, now we pop out 3 and 2 from stack as price and price are less than 80. `span` = 4-0 = 4. stack = [0,4].
On day 6, stock price is 85, now we pop out 4 from stack as price is less than 85. `span` = 5-0 = 5. stack = [0,5].
On day 7, the stock price is 200, now we pop out 5 and 0 from the Stack as price and price is less than 200. Now stack is empty, at this point, `span` = 6. stack = .

#### Stock span problem: Implementation

```
import java.util.Arrays;
import java.util.Stack;

/**
* Created by sangar on 18.9.18.
*/
public class StockSpan {
public static int[] stockSpan(int[] prices){

Stack<Integer> s = new Stack();
int[] span = new int[prices.length];

//Step 1. Initialization
span = 1;
s.push(0);

for(int i=1; i<prices.length; i++){
//Find the price on stack which is greater than current day's price
while(!s.empty() && prices[i] > prices[s.peek()]){
s.pop();

if(s.empty())
span[i] = i+1;
else
span[i] =  i - s.peek();

//Push current day onto top of stack
s.push(i);
}
}
return span;
}

public static void main(String args[]){
int prices[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98, 200};
int[] span = stockSpan(prices);

Arrays.stream(span).forEach(System.out::println);

}
}

```

If you want to understand the basic implementation of the Stack data structure, this is the C code for it.

```#include<stdio.h>
#include<stdlib.h>

#define STACK_SIZE 100

typedef struct stack{
int top;
int items[STACK_SIZE];
}stack;

void push(stack *ms, int item){
if(ms->top < STACK_SIZE-1){
ms->items[++(ms->top)] = item;
}
else {
printf("Stack is full\n");
}
}

int pop (stack *ms){
if(ms->top > -1 ){
return ms->items[(ms->top)--];
}
else{
printf("Stack is empty\n");
}
}
int peek(stack ms){
if(ms.top < 0){
printf("Stack empty\n");
return 0;
}
return ms.items[ms.top];
}
int isEmpty(stack ms){
if(ms.top < 0) return 1;
else return 0;
}

void stockSpan(int prices[], int days){

stack ms;
int i;

int span[days];

if(days ==0) return;

span = 1;
ms.top = -1;

push(&ms, 0);

for(i=1; i<days; i++){
while(!isEmpty(ms) && prices[i] > prices[peek(ms)])
pop(&ms);

if(isEmpty(ms)){
span[i] = i+1;
}
else{
span[i] =  i - peek(ms);
}
push(&ms, i);
}

for(i=0; i<days; i++){
printf("%d  ", span[i]);

printf("\n");
}
/* Driver program */
int main(){

//int prices ={100,60,70, 65, 85, 80};
int prices[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98, 200};

int n  = sizeof(prices)/sizeof(prices);

stockSpan(prices, n);
return 0;
}
```

The optimal time complexity of the stock span algorithm is `O(n)` along with a space-complexity of `O(n)`.

Now that you have learned the concept, can you solve the similar problems on HackerEarth