# Arrays - The Stock Market Problem

Classic interview questions on Arrays

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

### Question

Given 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.

```
Input: [3, 4, 5, 6, 1, 5]
Output: 4
```

### Method 1: Brute Force

In 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.

```
from typing import List
def maxProfit(prices: List[int]) -> int:
max_profit = 0
for i in range(len(prices)):
for j in range(i, len(prices)):
if(prices[j] - prices[i] > max_profit):
max_profit = prices[j] - prices[i]
return max_profit
print(maxProfit([3, 4, 5, 6, 1, 5]))
print(maxProfit([7, 1, 5, 3, 6, 4]))
"""
Output:
4
5
"""
```

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 Version

In 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.

```
from typing import List
import sys
def maxProfit(prices: List[int]) -> int:
min_price = sys.maxsize
max_profit = 0
for i in range(len(prices)):
if(prices[i] < min_price):
min_price = prices[i]
elif (prices[i] - min_price > max_profit):
max_profit = prices[i] - min_price
return max_profit
print(maxProfit([3, 4, 5, 6, 1, 5]))
print(maxProfit([7, 1, 5, 3, 6, 4]))
"""
Output:
4
5
"""
```

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`

.