Online Stock Span : 901 Leetcode

Stock span means how many times the stock stayed in a price lower than its own price.

Current index stayed 2 times smaller than its current price

Clearly from the figure the point where we stopped was the one whose price is greater than the price of current index.

Hence all we need to do is to find nearest larger element to current index.

To find nearest larger element we need to go through all the adjacent smaller elements and pop them one by one.

Thus the number of times we had to pop the smaller element will be the span of the stock.

State Diagram

Scenario 1 : Empty Stack

A stack can be or become empty in 2 cases :

1) When there are no elements and hence current index is 0 means current element is the first element.

2) Or all the elements are smaller than current index, in which case pop everything → stack gets empty

if (stack.isEmpty()) ans = index + 1;

Scenario 2: Non Empty Stack

We will keep on popping adjacent smaller elements until you either reach the end of stack or a larger element is encountered.

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

ans = index - stack.peek()[1];

Overall what we did is to a given index stack span is the count of elements which are smaller than the current index. We stored elements in stack and in order to pop smaller elements we compared peek with the current element.

Git: github.com/tanu02/LeetCode/blob/master/Stack/src/StockSpanner.java