LeetCode “Online Stock Span” Solution Using Monotonic Stack

LeetCode “Online Stock Span” Solution Using Monotonic Stack

56 / 100 SEO Score

Problem

Write 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].

Example 1:

Input:

["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]

Output:

[null,1,1,1,2,1,4,6]

Explanation:

First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.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 concept that we will be using to solve this problem is a Monotonic Stack.

Here the algorithm is:

 Whenever we encounter greater or equal element than the peek of the stack, then we pop the elements which do not obey the monotonic stack (monotonic-increasing) behavior. We push the current element into the stack.

We will push pairs {price, span} onto the stack. Each {price, span} represents an increasing sequence of prices/days with the largest price being the current price. When we see an element that is smaller than the top of the stack, then we can pop the stack and add it’s span to the current price’s span. We repeat this until the top of the stack is no longer smaller or equal to the current price.

Why a Monotonic Stack?

In short, it minimizes the number of comparisons by avoiding previously made comparisons (it allows us to use previously made comparisons).

When we encounter a new day, we can just compare the top of the stack which already has a span number of days compared, and that information is compacted into that pair. So for one simple comparison, we get all the previous comparisons made with that price.

This minimization of comparisons makes our runtime amortized O(1) per next() or O(N) in total for N days.

Complexity Analysis:

  • Run time: O(N).
  • Space: O(1).

 

Example Analysis:

Solution for LeetCode "Online Stock Span" using Monotonic Stack

Solution for LeetCode “Online Stock Span” using Monotonic Stack

Code: 

import java.util.ArrayDeque;
import java.util.Deque;

public class StockSpanner {

  private final Deque<int[]> stack;

  StockSpanner() {
    stack = new ArrayDeque<>();
  }

  private int next(int price) {
    int span = 1;

    while (!stack.isEmpty() && stack.peek()[0] <= price) {
      span += stack.pop()[1];
    }

    stack.push(new int[]{price, span});
    return span;
  }

  public static void main(String[] args) {
    StockSpanner ss = new StockSpanner();

    assert ss.next(100) == 1;
    assert ss.next(80) == 1;
    assert ss.next(60) == 1;
    assert ss.next(70) == 2;
    assert ss.next(60) == 1;
    assert ss.next(75) == 4;
    assert ss.next(85) == 6;
  }
}

 

Conclusion:

This problem is a nice one for technical interview questions because is tests basic knowledge of Stack data structure and basic algorithm knowledge

Problem Link: Here

Leave a Reply