# Arrays - The Stock Market Problem

Classic interview questions on Arrays

### 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(n2). 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`. I code.