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

Design an algorithm to find the maximum profit. You may complete at most one buy and one sell transaction. Choose a single day to buy one stock and a different day in the future to sell that stock.

Function Signature:

from typing import List

def max_profit(prices: List[int]) -> int:
    """
    Find the maximum profit by completing at most one transaction.

    Parameters:
    - prices: A list of stock prices on each day.

    Returns:
    - int: The maximum profit.
    """
    # Your code here

Example:

# 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.

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

Instructions:

  • Write the max_profit function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊