Stacks : Stock span problem

Stock span problem

We are given a list of prices of a stock for N number of days. We need to find the 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 will be {1, 1, 2, 1, 4, 5}
For first day span is always 1. In example we can see that for day 2 at 60, there is no day before it where price was less than 60. Hence span is 1 again. For day 3, 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 price was less than 65. Hope this example clarifies the problem.
Stock span problem is slightly complicated to understand but solution is pretty easy. 

Analysis

Now lets look at the solution. One solution which immediately comes into mind  is:
For every day, scan all days prior to it and increment the span till we get the price greater than given day. Simple implementation but with quadratic complexity.

From above implementation, we see that the day we are really interested in 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 hint? Yes, maintain a stack which contains prices 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.

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.
  4. If the price of stock on the day on top of stack is less than price of stock on current day, Pop the index from the stack.
  5. If the price of stock on the day on top of stack is greater than price of stock on current day, calculate the span as current day- day at the top of stack.
  6. Push the current day index on to stack.

Code

Complexity analysis

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s