Leetcode Problem 8: Maximum Stock Profit

Arrays, Reversing, Problem Solving, Coding Interviews Made Simple

3 min readJan 15, 2024

Problem

This problem was asked by Facebook.

Given an array of numbers representing the stock prices of a company in chronological order, write a function that calculates the maximum profit you could have made from buying and selling that stock once. You must buy before you can sell it.

For example, given [9, 11, 8, 5, 7, 10], you should return 5, since you could buy the stock at 5 dollars and sell it at 10 dollars.

Join 150K+ tech leaders and get insights on the most important ideas in AI straight to your inbox through my free newsletter- AI Made Simple

Step 1:Brute Force

The brute force solution here is to iterate over our list of stock prices, and for each price, find the largest profit you can make from selling that stock price (with the formula future — current), and keep track of the largest profit we can find. You should be able to code it up on your own in 5–10 minutes at most.

def buy_and_sell(arr):
    max_profit = 0
    for i in range(len(arr) - 1):
        for j in range(i, len(arr)):
            buy_price, sell_price = arr[i], arr[j]
            max_profit = max(max_profit, sell_price - buy_price)
    return max_profit

This solution takes O(n²) time and constant space. How do we improve it?

Step 2: Analyzing What We Are Given

The hard part about stock trading is that we never know when it will peak. This is not a problem for this question. We are given all the prices over a time period. Furthermore, we only need to maximize one single trade, not the overall profit.

So what do we do?

We are given an additional rule. We have to buy a stock before we can sell it. Which means for any given selling price/point, we can only calculate the profit taking a buying point to the left.

The maximum profit comes from the greatest difference between the highest price and lowest price, where the higher price must come after the lower one. But if we see a high price x and then a higher price y afterwards, then we can always discard x. So, if we keep track of the highest price in the future for each variable, we can immediately find how much profit buying at that price can make.

That means we can look at the array backwards and always keep track of the highest price we’ve seen so far. Then, at each step, we can look at the current price and check how much profit we would have made buying at that price by comparing with our maximum price in the future. Then we only need to make one pass!

def buy_and_sell(arr):
    current_max, max_profit = 0, 0
    for price in reversed(arr):
        current_max = max(current_max, price)
        potential_profit = current_max - price
        max_profit = max(max_profit, potential_profit)
    return max_profit

This runs in O(N) time and O(1) space.

Save the time, energy, and money you would burn by going through all those videos, courses, products, and ‘coaches’ and easily find all your needs met in one place at ‘Tech Made Simple’! Stay ahead of the curve in AI, software engineering, and the tech industry with expert insights, tips, and resources. 20% off for new subscribers by clicking this link. Subscribe now and simplify your tech journey!