## Stock Span Problem- Stock Span Problem is a financial problem.
- In this problem, we are provided with the ' n ' number of stocks with their corresponding prices.
- These prices of the stocks are daily, and we just need to compare the stock prices.
- In this stock span problem, we need to determine the number of stocks that have an equal or lesser price than the current stock until we reach the stock greater than the current stock.
- This problem is mainly asked in the interviews of Amazon and Google, and the candidate must answer this problem in the duration of time through programming.
- The term stock span is defined as the number of consecutive stocks before the current stock when the price of the prior stocks is less than or equal to the current stock's price.
Suppose we have provided an array of 10 stocks; these stocks refer to the corresponding prices of the stocks daily.
Now, we will store all these stock prices in an array named as -
Now, manually let us find out the result -
170 <= 170 ; True 150 <= 170 ; True We will
180 <= 180 ; True 170 <= 180 ; True 150 <= 180 ; True We will
80 <= 80 ; True 180 <= 80 ; False We will
85 <= 85 ; True 80 <= 85 ; True 180 <= 85 ; False We will
90 <= 90 ; True 85 <= 90 ; True 80 <= 90 ; True 180 <= 90 ; False We will
100 <= 100 ; True 90 <= 100 ; True 85 <= 100 ; True 80 <= 100 ; True 180 <= 100 ; False We will
110 <= 110 ; True 100 <= 110 ; True 90 <= 110 ; True 85 <= 110 ; True 80 <= 110 ; True 180 <= 110 ; False We will
75 <= 75 ; True 110 <= 75 ; False We will
95 <= 95 ; True 75 <= 95 ; True 110 <= 95 ; False We will Hence final output will be -
Here we can observe that for an nth term, we require n comparisons, n-1 for previous ones, and 1 for itself; hence total n comparisons require nth term. ## Methods to solve Stock Span Problem -- By using the Brute force approach, an inefficient method.
- By using Stack, an efficient method
- By using multiple stacks
- Linear complexity method, without using Stack
Let us start solving this Stock span problem using these methods. ## Method # 1 Brute Force approach, an inefficient method -Although this method is not so efficient, it is very easy to implement to solve any problem. If you want to understand the basic criteria, you first implement any program using the Brute force method. Once you have succeeded in making the program, then try to find the other best alternative to solve the given problem, in much more efficient way, whose performance is also better and time complexity is also less then this method. Let us discuss the stock span problem using this method: As we have already seen, the working of the stock span problem is to find the number of stocks, which are less than or equal to the target stock. Thus, we called it finding the Span of that stock. ## Algorithm to implement Brute force method to solve this problem -
## Implementation of Stock Span Problem using Method # 1 in C Programming Language
## Implementation of Stock Span Problem using Method # 1 in C++ Programming Language
## Implementation of Stock Span Problem using Method # 1 in Java Programming Language
## Implementation of Stock Span Problem using Method # 1 in Python Programming Language
## Implementation of Stock Span Problem using Method # 1 in C# Programming Language
1 1 2 4 5 1 After executing the program successfully in a specific programming language and following the Brute force algorithm using the nested traversal approach, we will get the proper result, i.e., finding out the span values for given stock prices daily. Now let us analyze the running time and performance of the algorithm we are applying to get the span values for corresponding stock prices by finding the algorithm's time complexity and space complexity using in Method # 1. ## Time Complexity of Method # 1 -For finding the time complexity, we need to observe the algorithm and analyze the time taken by a particular line for execution. We can observe that we require traversing the stock price array nested one loop in another loop; one traversal of the loop for traversing the stock prices from 1 to n - 1 stock prices, and the second loop is for comparing the stock price from previous stock prices until we get the stock price greater than the current stock price, and simultaneously incrementing the values of Span for corresponding stock prices in span array, finally in this way we require nested loop traversing. Hence time complexity will be - T ( n ) = O ( n ).O ( n )
Hence time complexity will be O ( n ## Space Complexity of Method # 1 -To find space complexity, we need to observe the program and analyze the space required to store all the variables; as we notice the program, we will observe that for storing span values of corresponding ' n ' stock prices, we require an array of ' n ' variables to store ' n ' span values.
Hence the space complexity for above method # 1 will be O ( n ). ## Method # 2 By Using Stack, an efficient method -This method is very efficient compared to the previous Brute force method because the time complexity in the brute force approach is O ( n Let us discuss the stock span problem using this method: As we have already seen, the working of the stock span problem is to find the number of stocks, which are less than or equal to the target stock. Thus, we called it finding the Span of that stock. ## Algorithm to implement Stack method to solve this problem -
## Implementation of Stock Span Problem using Method # 2 in C++ Programming Language
## Implementation of Stock Span Problem using Method # 2 in Java Programming Language
## Implementation of Stock Span Problem using Method # 2 in Python Programming Language
## Implementation of Stock Span Problem using Method # 2 in C# Programming Language## The output of the following C# program for solving the Stock span problem using Method # 21 1 2 4 5 6 After executing the program successfully in a specific programming language and following the Brute force algorithm using the nested traversal approach, we will get the proper result, i.e., finding out the span values for given stock prices daily. Now let us analyze the running time and performance of the algorithm we are applying to get the span values for corresponding stock prices by finding the algorithm's time complexity and space complexity using in Method # 2. ## Time Complexity of Method # 2 -For finding the time complexity, we need to observe the algorithm and analyze the time taken by a particular line for execution. We can observe that we require traversing the stock price array using one loop only; traversal of the loop for traversing the stock prices from 1 to n - 1 stock prices, and inside that loop, we are using a stack data structure to hold the span values and for doing comparisons among these stock prices of different days. Hence time complexity will be - T ( n ) = O ( n ) + C Here, ' C ' be any constant.
Hence time complexity will be O ( n ), as we do the asymptotically rough idea that we require ' n ' time to solve the problem of ' n ' elements. ## Space Complexity of Method # 2 -To find space complexity, we need to observe the program and analyze the space required to store all the variables; as we notice the program, we will observe that for storing span values of corresponding ' n ' stock prices, we require an array of ' n ' variables to store ' n ' span values.
Hence the space complexity for above method # 2 will be O ( n ). ## Method # 3 By Using Multiple Stacks -The implementation of this method is quite different from the method 2. We will see it further in the analysis of the algorithm. Let us discuss the stock span problem using this method: As we have already seen, the working of the stock span problem is to find the number of stocks, which are less than or equal to the target stock. Thus, we called it finding the Span of that stock. ## Algorithm to implement Multiple Stack method to solve this problem -
## Implementation of Stock Span Problem using Method # 3 in C Programming Language
Now let us analyze the running time and performance of the algorithm we are applying to get the span values for corresponding stock prices by finding the algorithm's time complexity and space complexity using in M ethod # 3. ## Time Complexity of Method # 3 -For finding the time complexity, we need to observe the algorithm and analyze the time taken by a particular line for execution. We can observe that we require two stacks for executing this stock span problem, one Stack is needed to store the stock prices of corresponding days; and another stack is needed to store the temporary values of Span, calculated by further comparisons between the stock prices, and finally, we have store these span values in an array. Hence time complexity will be - T ( n ) = O ( n ) + C Here ' C ' be any constant.
Hence time complexity will be O ( n ), as we do the asymptotically rough idea that we require ' n ' time to solve the problem of ' n ' elements. ## Space Complexity of Method # 3 -To find space complexity, we need to observe the program and analyze the space required to store all the variables; as we notice the program, we will observe that for storing span values of corresponding ' n ' stock prices, we require an array of ' n ' variables to store ' n ' span values.
Hence the space complexity for above method # 3 will be O ( n ). ## Method # 4 Linear Complexity method, without using Stack -This method is very efficient compared to the previous Brute force method because the time complexity in the brute force approach is O ( n Let us discuss the stock span problem using this method: ## Algorithm to implement linear-complexity method without using Stack to solve this problem -
## Implementation of Stock Span Problem using Method # 4 in C Programming Language
## Implementation of Stock Span Problem using Method # 4 in C++ Programming Language
## Implementation of Stock Span Problem using Method # 4 in Java Programming Language
## Implementation of Stock Span Problem using Method # 4 in Python Programming Language
## Implementation of Stock Span Problem using Method # 4 in C# Programming Language
1 1 2 4 5 1 After executing the program successfully in a specific programming language and following the linear complexity algorithm without using Stack, we will get the proper result, i.e., finding out the span values for given stock prices daily. Now let us analyze the running time and performance of the algorithm we are applying to get the span values for corresponding stock prices by finding the algorithm's time complexity and space complexity using in Method # 4. ## Time Complexity of Method # 4 -For finding the time complexity, we need to observe the algorithm and analyze the time taken by a particular line for execution. We can observe that we require traversing the stock price array using one loop; for traversal of the loop for traversing the stock prices from 1 to n - 1 stock prices, and while condition loop is for comparing the stock price from previous stock prices until we get the stock price greater than the current stock price, and simultaneously incrementing the values of Span for corresponding stock prices in span array, finally in this way we require nested loop traversing. Hence time complexity will be - T ( n ) = O ( n ) + C
Hence time complexity will be O ( n ), as we do the asymptotically rough idea that we require ' n ' time to solve the problem of ' n ' elements. ## Space Complexity of Method # 4 -
Hence the space complexity for above method # 4 will be O ( n ). |

For Videos Join Our Youtube Channel: Join Now

- Send your Feedback to [email protected]