Stock Market

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