Online Stock Span

In this blog, we will solve the LeetCode problem #901, Online Stock Span.

Introduction

 

In this article, we will sove the leetcode problem #901, Minimum Falling Path Sum. The problem statement goes like this: Construct a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6]. And here is how it's called using C#,

static void Main(string[] args)
{
    var stockSpanner = new StockSpanner();
    var prices = new int[] { 100, 80, 60, 70, 60, 75, 85 };
    var result = new List<int>();
    foreach (var price in prices)
        result.Add(stockSpanner.Next(price));
    //result = [ 1, 1, 1, 2, 1, 4, 6]
}

Note that (for example) stockSpanner.Next(75) returned 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.

 

Solution

 

The most naive approach to this problem is by using stacks to store all the prices and then finally comparing them with the last price. If the current price is more than the last stored price we switch them and push the stack. Here is the C# code for the approach,

class StockSpanner
{
    Stack<int[]> Stack;

    public StockSpanner()
    {
        Stack = new Stack<int[]>();
    }
    public int Next(int price)
    {
        int result = 1;
        while (Stack.Count != 0 && Stack.Peek()[0] <= price)
        {
            result += Stack.Pop()[1];
        }
        Stack.Push(new int[] { price, result });
        return result;
    }
}