Best Time to Buy and Sell Stock — Day 21(Python)

Photo by Markus Winkler on Unsplash

Today’s question is another easy tagged question from leetcode. Let us jump into the problem without wasting much time.

121. Best Time to Buy and Sell Stock

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, hence max profit = 0.

One way to solve the given problem is by finding the profits by considering all buy and sell options. How do we do that?

Consider the first number as a buy option. Consider all numbers after buy as sell options.
Find the difference between sell value and buy value. The profit earned would be a positive number. If we get no positive number, return 0.
The max among the profit earned is our result.

class MaxProfitFinder:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for first in range(len(prices)):
            for second in range(first+1, len(prices)):
                profit = max(profit, prices[second] - prices[first])
        return profit

Complexity analysis

Time Complexity

We have two for loops which traverse through the entire list of prices twice. Hence the time complexity is O(N²), where N is the length of prices list.

Space Complexity

We are not using any extra space while implementing the algorithm, and hence the space complexity is O(1).

How should we improve the time complexity?

Can we try to implement the solution using one pass?

Initialize buy value as infinity, and profit earned as 0.

Traverse through each value, check if the current value is less than buy. If yes, the current number will be the buy value.

If no, check if the difference between the current value and buy value is higher than the profit. If yes, the difference between the current number and buy value is our profit.

class MaxProfitFinder:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        profit = 0
        for i in range(len(prices)):
            if prices[i] < min_price:
                min_price = prices[i]
            else:
                profit = max(profit, prices[i] - min_price)
        return profit

Complexity analysis

Time Complexity

We have one for loops which traverse through the entire list of prices. Hence the time complexity is O(N), where N is the length of prices list.

Space Complexity

We are not using any extra space while implementing the algorithm, and hence the space complexity is O(1).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.