Best Time to Buy and Sell Stock in Python

You can find the leetcode problem here.

Question:

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Brute Force Solution:

I would use a nested for loop to compare a number and the other numbers to the right of it to find the max profit.

def maxProfit(prices):
        max_profit = 0

        for earlier_price in range(len(prices)):
            for later_price in range(earlier_price + 1, len(prices)):
                if profit < prices[later_price] - prices[earlier_price]:
                    max_profit = prices[later_price] - prices[earlier_price]
        return max_profit

I'm updating the max_profit whenever I find a profit that is greater. For my for loops, I don't want to count the numbers to the left of the eariler_price and I don't want to double count the eariler_price. To prevent this I increased the beginning range by 1 (earlier_price + 1).

If you copy and paste this solution into leetcode it will give you time exceeded because this algorithm runs in O(n^2) time and o(1) space. We are essentially looping through once for each number times all the other numbers.

Optimal Solution:

We are going to keep track of the max_profit and the minimum number that we have seen so far. We are going to loop through each number in the list, and see if there is a lower number than our minimum_num. If there is, we reassign the minimum_num. We also decide if the max_profit stays the same or if we reassign it with our new calculated profit. This algorithm doesn't make new space and only goes through the list once.

def maxProfit(prices):
        max_profit = 0
        minimum_num = 100000

        for num in prices:
            if num < minimum_num:
                minimum_num = num
            max_profit = max(max_profit, num - minimum_num)
        return max_profit

You might be wondering why is our minimum_num so high? Where did you get this number from? This is a very high number I set because if I were to set the minimum_num to be 0, then it might be lower than anything in our list. You could also set the minimum_num to the first number in the list too. The minimum_num will most likely be replaced in the first iteration of our loop.

max_profit = max(max_profit, num - minimum_num)

I believe this is the most important step in this algorithm because it's where you decide whether to update max_profit or not.

Conclusion

This algorithm uses the Greedy Approach, which says that we are going to have a variable/variables that we will update as we find something better.

Thank You for reading!