Stock span problem implementation

Stock span problem

We are given a list of prices of a stock for N number of days. We need to find stock span for each day. Span is defined as number of consecutive days before the given day where the price of stock was less than or equal to price at given day. For example, {100, 60,70,65, 80, 85} span for each day will be {1, 1, 2, 1, 4, 5}.

For first day span is always 1. In example, notice that on day 2, price of stock is 60 and there is no day prior to it where price was less than 60. Hence span for day 2 is 1 again. For day 3, price at day 2 (60) is less than 70, hence span for day 3 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 price was less than 65. Hope this example clarifies the problem. Stock span problem is slightly complicated to understand but solution is pretty easy.
One solution which immediately comes into mind  is:  For every day, scan all days prior to it and increment span till price greater than given day is seen. Simple implementation but with quadratic complexity.

From above implementation, notice that the day of real interested  to us is the day where price was last seen greater than current day price. So we need to check last price which was greater than price today. Getting some hints? Yes, maintain a stack which contains prices seen in decreasing order.

So while scanning prices on given days, check if there are prices which are less than current price. If yes, just pop them out. When you encounter a price which is greater than current price, stock span with maximum profit of current day is difference between day of that price and current day.  So looking carefully, it becomes apparent that, storing index of last greatest seen price would make things easier as compared to storing actual price. Hence day is store i on stack, price[i] will give us the price of stock on day i.

Refer stack data structure to understand basics of stack.

Algorithm to detect stock span

1. Initialize span of day 1 as 1.
2. Put day 1 on to stack. 
3. For all days starting from day 2, repeat following steps. 
   3.1 If price of stock on day at top of stack is less than price of stock on current day, Pop the index from stack. 
   3.2 If price of stock on the day on top of stack is greater than price of stock on current day, calculate span as current day - day at top of stack. 
   3.3 Push current day index on to stack.

Figure below explains algorithm in action
stock span problem

Stock span algorithm

package Problems;
 
import common.Stack;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 * Created by Sangar on 24-08-2015.
 */
public class StockSpanDemo {
    public static void main(String[] args){
        List<Integer> stockPriceList = new ArrayList<Integer>();
        stockPriceList.add(100);
        stockPriceList.add(60);
        stockPriceList.add(70);
        stockPriceList.add(65);
        stockPriceList.add(80);
        stockPriceList.add(85);
 
        List<Integer> stockSpanList = getStockSpan(stockPriceList);
        System.out.println(stockSpanList);
 
    }
    static List<Integer> getStockSpan(List<Integer> stockPriceList){
        List<Integer> stockSpanList = new ArrayList<Integer>();
 
        stockSpanList.add(0,1);
        Stack s = new Stack();
        s.push(0);
 
        for(int i=1; i<stockPriceList.size(); i++){
 
            while(!s.isEmpty() && 
                 stockPriceList.get(s.top())< stockPriceList.get(i)){
                s.pop();
            }
            stockSpanList.add(i, i-s.top());
 
            s.push(i);
        }
        return stockSpanList;
    }
}

Stack implementation

/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Stack
{
	private int top;
	private ArrayList<Integer> elements;
	public void Stack(){
		top = -1;
		elements = new ArrayList<Integer>();
	}
 
	void push(int element){
		top++;
		elements.add(element);
	}
 
	int pop(){
		if(top > -1){
			int element = elements.get(top--);
			return element;
		}
		else{
			System.out.println("Stack is empty");		
		}
		return -1;
	}
 
	int peek(){
		if(top > -1)
			return elements.get(top);
		else{
			System.out.println("Stack is empty");		
		}
		return -1;
	}
 
	boolean iEmpty(){
		if(top > -1)
			return false;
		return true;
	}
 
}

Stock span problem implementation in C

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

Complexity of stock span with maximum profit is O(N).

Please share your thoughts in comments, if something is not correct. Sharing is caring.

  • http://dvsathish.wordpress.com Sathish

    Nice solution!!!

    I have provided my solution below.

    public static int[] StockSpan(int[] input)
    {
    if (null == input || input.Length == 0)
    return null;

    int[] output = new int[input.Length];
    int inLength = input.Length;

    for (int i = 0; i = 0; j–)
    {
    if (input[j] <= input[i])
    output[i] = output[i] + 1;
    else
    break;
    }
    }
    return output;
    }

  • Sampath Kumar

    Nice post.

  • Pingback: Stack data structure c implemetation - Algorithms and Me()