[Solution]Problem 8: Maximum Stock Profit[Facebook]

Medium

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.

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^2) 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.

——————————————————————————————————————.

Bonuses/Promotion (Get Free Stuff)

To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:

Reach out to me on Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/