Stacks : Stock span problem

Stock span problem

Stock span problem is commonly asked in Google and Amazon interviews and taught as the application of stack data structure in universities. Let’s define the problem :

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}.

stock span problem

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 why span for day 4 is 1 even though there was a day 2 where the price was less than 65.

stock span problem example

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. Simple implementation, however complexity is O(n2) where n is number of days.

If we observe the brute force algorithm, it is evident that we are interested in a day which has stock price was 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. Getting some hint? 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 stack elements should be in increasing order of price. The element at the top should be the maximum price seen till 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, stock span of the current day is the difference between the day of price on top of the stack and current day.
Storing index of last greatest stock price would make things easier as compared to storing actual stock price on the stack. Hence day is store i on stack, price[i] will give us the price of stock on day i.

Stock span problem : Algorithm

  1. Initialize span of day 1 (i=0) as 1 and put on to 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 algorithm, we will put span[0] = 1 and stack will be [0].
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] = 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[1] = 60. So span[2] = 2 – 0 = 2. Push new price on stack, stack = [0,2]
On day 4, stock price is 65. price[stack.top()] > price[3], so span[3] = 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[2] and price[3] are less than 80. span[4] = 4-0 = 4. stack = [0,4].
On day 6, stock price is 85, now we pop out 4 from stack as price[4] is less than 85. span[5] = 5-0 = 5. stack = [0,5].
On day 7, stock price is 200, now we pop out 5 and 0 from stack as price[5] and price[0] are less than 200. Now stack is empty, at this point, span[6] = 6. stack = [6].

Stock span problem : Implementation

package com.company;

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[0] = 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 stack data structure, this is the C code for you.

#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[0] = 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[6] ={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[0]);
 
 stockSpan(prices, n);
 return 0;
}

Complexity of stock span algorithm is O(n) along with space complexity of O(n).

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

Please reach out if there is anything missing or wrong. If you are interested in taking coaching by our experienced software engineers, please contact us, We would be glad to help you.