121. Best Time to Buy and Sell Stock#

Difficulty: Easy

Link to Problem: To see the Best Time to Buy and Sell Stock problem on LeetCode, click here!

You are given an array prices where prices[i] is the price of a given stock on the \(i^{th}\) 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 <= \(10^5\)

  • 0 <= prices[i] <= \(10^4\)

Solution:#

Here’s a Python function to solve this problem:

def maxProfit(prices):
    if not prices:
        return 0
    
    min_price = prices[0]
    max_profit = 0
    
    for price in prices:
        # Update the minimum price if a lower price is encountered
        min_price = min(min_price, price)
        # Calculate the profit if selling at the current price
        max_profit = max(max_profit, price - min_price)
    
    return max_profit

Explanation:#

  • The maxProfit function takes a single argument, prices, which is a list of stock prices.

  • The first line of the function checks if the prices list is empty. If it’s empty, there are no prices to analyze, so the function returns 0 (no profit can be made).

  • Then, we initialize two variables:

    • min_price: This variable will keep track of the minimum price seen so far. We initialize it with the price of the first day in the list (prices[0]).

    • max_profit: This variable will keep track of the maximum profit we can achieve. We initialize it to 0 because initially, we haven’t made any profit.

  • We start iterating through the prices list, where price represents the stock price for the current day.

  • In each iteration, we check if the current price is lower than the min_price we’ve seen so far. If it is, we update min_price to the current price. This is because we want to buy the stock at the lowest possible price.

  • Next, we calculate the profit we would make if we sold the stock at the current price (assuming we bought it at min_price). We do this by subtracting min_price from the current price. This represents the profit for the current day.

  • We also use the max function to keep track of the maximum profit seen so far. If the profit calculated for the current day is greater than the max_profit we’ve seen previously, we update max_profit with this higher value.

  • Finally, after iterating through all the days in the prices list, we return max_profit, which represents the maximum profit that can be achieved by buying and selling a single stock.

Test cases#

# Example 1:
prices1 = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices1))

5

# Example 2:
prices2 = [7, 6, 4, 3, 1]
print(maxProfit(prices2))

0

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code:

Time Complexity:

  • The code iterates through the prices array once, examining each price exactly once.

  • Within the loop, there are constant-time operations such as comparisons, additions, and subtractions.

  • Therefore, the time complexity of this code is O(n), where n is the length of the prices array. It performs a linear number of operations relative to the size of the input.

Space Complexity:

  • The space complexity of the code is constant, O(1).

  • Regardless of the size of the input prices array, the code only uses a fixed amount of additional memory to store two variables (min_price and max_profit) and a few loop variables.

  • The memory usage does not depend on the size of the input, so it is considered constant space complexity.

In summary:

  • Time Complexity: O(n) where n is the length of the prices array.

  • Space Complexity: O(1) (constant space usage).

Challenging Exercises:#

  1. Multiple Transactions Allowed: Modify the problem to allow multiple transactions (buy and sell multiple times), but you must sell before buying again. Find the maximum profit in this scenario.

  2. K Transactions Allowed: Extend the problem to allow at most k transactions. Find the maximum profit considering this constraint.

  3. With Transaction Fee: Introduce a transaction fee for each buy/sell operation. Modify the code to maximize profit while considering the transaction fee.