Online Stock Span
Introduction
Design an algorithm that 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 in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.
-
For example, if the prices of the stock in the last four days is
and the price of the stock today is[7,2,1,2]
, then the span of today is2
because starting from today, the price of the stock was less than or equal4
for2
consecutive days.4
-
Also, if the prices of the stock in the last four days is
and the price of the stock today is[7,34,1,2]
, then the span of today is8
because starting from today, the price of the stock was less than or equal3
for8
consecutive days.3
Implement the StockSpanner
-
Initializes the object of the class.StockSpanner()
-
Returns the span of the stock's price given that today's price isint next(int price)
.price
Example 1
[[], [100], [80], [60], [70], [60], [75], [85]]
Output: [null, 1, 1, 1, 2, 1, 4, 6]
Explanation:
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85); // return 6
Constraints:
1 <= price <= 105
- At most
calls will be made to104
.next
Solution 1 - Using stack, construct a monotonically decreasing stack
In this approach, we are going to build a monotonically decreasing stack, meaning that elements in the stack should be in a decreasing order, when we see a number higher than the top of the stack, then we delete elements from stack to ensure that the stack is still monotonically decreasing order.
Let's understand this with an example prices = [100, 80, 60, 70, 60, 75, 85]
- To start with, lets declare a stack that we will be using to store price and its span as pair of numbers.
-
First element price is
and the stack is empty, so the span for this price is100
. So, we will add1
as a pair into the stack (price , its span).[100,1]
-
Second element price is
, and the stack's top element is greater than this, so the span for this is going to be80
. So, we will add1
into the stack.[80,1]
-
Third element price is
, and the stack's top element is greater than this, so the span for this is going to be60
. So, we will add1
into the stack.[60,1]
-
Fourth element price is
, and the stack's top element70
is less than this, so take the span of previous smaller element, and add it to current elements span, so the span becomes60
, we will check next element from the stack, it is2
, since this is greater than80
, we don't do anything. We will just remove the smaller element that we found, i.e.70
and add60
into the stack.[70,2]
-
Fifth element price is
, and the stack's top element is greater than this, so the span for this is going to be60
. So, we will add1
into the stack.[60,1]
-
Sixth element price is
, and the stack's top element75
is less than this, so take the span of previous smaller element, and add it to current elements span, so the span becomes60
, we will check next element from the stack, it is1 (current element) + 1 (previous smaller) = 2
, this is also smaller, so take the span of previous smaller element, and add it to current elements span, so the span becomes70
, next element from the stack is2 (current) + 2 (previous) = 4
, since this is greater than80
, we don't do anything. We will just remove the smaller elements that we found, i.e.75
and60
, and add70
into the stack.[75,4]
-
Sixth element price is
, and the stack's top element85
is less than this, so take the span of previous smaller element, and add it to current elements span, so the span becomes75
, we will check next element from the stack, it is1 (current element) + 4 (previous smaller) = 5
, this is also smaller, so take the span of previous smaller element, and add it to current elements span, so the span becomes80
, next element from the stack is5 (current) + 1 (previous) = 6
, since this is greater than100
, we don't do anything. We will just remove the smaller elements that we found, i.e.85
and75
, and add80
into the stack.[85,6]
-
Since we are constructing a monotonically decreasing stack, each time a larger element found, we are going back into the stack until the elements that are smaller or equal to this,
then replacing all smaller elements prior with current one, so for the next element which larger than current, we are not going back again to all the way to all prior smaller elements, so the time complexity is going to be
.O(n)







Implementation steps:
-
First, we will create a variable
apriceSpanPair
which will store stock price and the span as a pair of numbers.Stack
-
Next, each time a
method is called, calculate the span using the below logic:next(int stock)
-
Initalize a variable
, then look at spans fromspan = 1
stack and if the stock price is less than current one, then add that span to current span. For example if previous stock ispriceSpanPair
and the current stock is10
, we can add previous span count as well.11
-
If the previous price's span is added, i.e. if the previous price is less than or equal to current price, we can remove that element from
and add current element along with its span as a pair. This is an important step, because if the current price is less than previous price, there is no need to remove previous element and the span for current pday price is going to be 1, but whenever the next bigger price is seen, we can add span from previous prices in a cumulative fashion, and remove previus elements, so that the loopup range for next element is already pre-computed.priceSpanPair
-
Return
as the answer.span
import java.util.Stack;
public class StockSpanner {
final Stack<int[]> priceSpanPair; // each array will have two values -> price, span
public StockSpanner() {
priceSpanPair = new Stack<>();
}
public int next(int price) {
int span = 1;
while(!priceSpanPair.isEmpty() && priceSpanPair.peek()[0] <= price) {
span += priceSpanPair.peek()[1];
priceSpanPair.pop();
}
priceSpanPair.push(new int[]{price, span});
return span;
}
public static void main(String[] args) {
StockSpanner stockSpanner = new StockSpanner();
System.out.println(stockSpanner.next(100));
System.out.println(stockSpanner.next(80));
System.out.println(stockSpanner.next(60));
System.out.println(stockSpanner.next(70));
System.out.println(stockSpanner.next(60));
System.out.println(stockSpanner.next(75));
System.out.println(stockSpanner.next(85));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n
next
Space complexity: O(n) for the stack.
Above implementations source code can be found at