Arrays - The Stock Market Problem
Classic interview questions on Arrays
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
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).
In this version, our aim is to just use 1 for loop to get the answer.
We track 2 variables here,
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
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,