⌚121. Best Time to Buy and Sell Stock

Easy | Grind 75 | August 16th Tuesday, 2022

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Constraints:

• 1 <= prices.length <= 105

• 0 <= prices[i] <= 104

Example 1

Input: prices = [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. Note that buying on day 2 and selling on day 1 is
not allowed because you must buy before you sell.

Example 2

Input: prices = [7,6,4,3,1]
Output:0
Explanation: In this case, no transactions are done and the max profit = 0.

SOLUTION

At any index, maximum profit from the price list will be the difference between the minimum value up to the index and the maximum value from that minimum onwards until the index. For instance in example one, if we were find the maximum profit at index 3, we see that the minimum value is 1 and the maximum value after 1 is 5. So the maximum profit you can make at index 3 is 5-1=4.Given this idea, we iterate over the list and keep track of the minimum value we have seen. For each element after the minimum, we will calculate the profit by selling at the current element's price and keep track of the maximum profit. Whenever we encounter a new minimum, we know that we can increase our profit potential by always buying at the current minimum price point rather than the old minimum.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_val = 0 
        
        #set the first value as the minimum
        minimum = prices[0]
        
        # iterate over prices
        for i in range(1, len(prices)):
            # we found a new minimum. current price is lesser than the previous day
            if prices[i] < minimum: 
                minimum = prices[i]
                
            # current price is equal or more than the minimum: meaning profit can be made
            else: 
                max_val = max(max_val, prices[i]-minimum)
        
        return max_val 

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the number of elements. We iterate the prices list once.

SPACE: O(1) space is constant since we only use two variables to store the minimum and the maximum regardless of the list size.

*written with help from OpenAI GPT-3 model