# Stock Market

Leetcode link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

### #

QuestionGiven an array of stock prices, we need to find the maximum profit that can be generated over the time window.

Let's say Company A has gone public. We represent the stock prices of Company A as an array - `[3, 4, 5, 6, 1, 5]`

. On Day 0, the price was \$3. On Day 1, it was \$4 and so on.

Let's say I am a trader who analyses the stock prices and says how much is the maximum profit I could have made in the time period. In this case, it will be $4. I will buy on the 5th day when the price was just \$1 and sell the stock the next day for \$5, giving me a profit of \$4.

### #

Method 1: Brute ForceIn the brute force method, the solution is simple. We will find the maximum difference we can get from buying a stock on a particular day and selling it on another using 2 `for`

loops.

While that's a quick implementation, it has a time complexity of O(n^{2}). Space complexity is just O(1) in constant time as we only have a `max_profit`

variable to keep track of the maximum profit at any point in time.

Let's try to optimise our time complexity to O(n).

### #

Optimised VersionIn this version, our aim is to just use 1 for loop to get the answer.

We track 2 variables here, `min_price`

and `max_profit`

. For each element in the list, we check if it is smaller than the current `min_price`

and if so, we update `min_price`

. Else, we check if the difference between the `min_price`

and the current element is more than the current `max_profit`

. If so, we update `max_profit`

.

Eventually, after the for loop finishes iterating through the list, we return the last updated `max_profit`

. If there was no way a profit could have been made, `0`

will be returned.

As discussed, this will have a time complexity of O(n) as we only iterate the list of stock prices exactly once and we use a space complexity of O(1) as we just keep track of the 2 variables, `min_price`

and `max_profit`

.