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

Avatar
Harish V
Software Engineer + Tech Enthusiast

I code.

comments powered by Disqus

Related