Last Updated: 16 Jun, 2022
Stock Span
Moderate
Asked in companies
Afzal has been working with an organization called 'Money Traders for the past few years. The organization is in the money trading business. His manager assigned him a task.
Given an array ’prices’ which denotes stock prices for ’n’ days, e.g., 'prices[ i ]' = price of the stock at ‘ith’ day, Find the stock's span for each day.
The span of the stock's price today is defined as the maximum number of consecutive days(starting from today and going backward) for which the price of the stock was less than today's price.
Example:
Input: ‘n’ = 7, ‘prices’ = [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]
Explanation:
On the sixth day, when the stock price was 75,
The span came out to be 4 because the last three prices(plus today) were less than the current or the sixth day's price.
Similarly, we can deduce the remaining results.
Note:
You don’t need to print anything. Just implement the given function
Input Format:
The first line of each test case contains an integer ‘n’ denoting the number of days.
The second line of each test case contains ‘n’ integers denoting the prices of the stocks.
Output format:
Return an array that contains the stock’s span for each day.
Approaches
In the naive approach, We can iterate over the prices array. For the ‘ith’ day, we can start iterating over the previous prices starting from (i-1)th day, and then for each last day, if the price is less than the price of the ith day, then we increase the span of the ith day by 1 otherwise we stop iterating over the previous prices.
The steps are as follows:-
Function findStockSpans(vector<int>& prices):
- Declare an ‘ans’ array to store the stock span for each day
- Iterate over the ‘prices’ array, for i = 0…n.
- Initialize a variable ‘span’ = 1. Variable ‘span’ will store the span for the ‘ith’ day
- Start Iterating over previous prices starting from the i-1th day, for j = i-1…0:
- If the price of the ith day is greater than that of the jth day, then increment the ‘span’ variable by 1.
- Otherwise, break since we need only consecutive days.
- Return the ‘ans’ array.
We can use a monotonic stack to find the closest previous day with a price greater than or equal to the current day's price. Then we iterate over the ‘prices’ array, and for the ith day total span is calculated as i - the previous day (with a price greater than or equal to that of the ith day). Because all the days between them will be consecutive and their prices will be smaller than that of ith day.
The steps are as follows:-
Function findStockSpans(vector<int>& prices):
- Declare a stack named ‘monotonicStack’.
- Declare an ‘ans’ array and initialize it with -1. It will store the stock span for each day.
- Iterate over the prices array in reverse, for i = n-1 … 0
- Repeat while ‘monotonicStack’ is not empty and the price of the ‘i’th day is greater or equal to the price of the day that is at the top of the stack
- The Stock Span for the day at the top of the stack is given by: the index of the day at the top - current index.
- Assign the span value of the day at the top of the stack to the 'ans' array.
- Pop out the top element
- Repeat while ‘monotonicStack’ is not empty and the price of the ‘i’th day is greater or equal to the price of the day that is at the top of the stack
- Push ‘i’ into the stack.
- Iterate over the 'prices’ array, for i = 0…n
- If the span of the ith day is -1, then assign it to 'i' + 1’.
- Return the ‘ans’ array