Buy and Sell Stock [Solution]

The problem of finding the maximum profit by completing at most one transaction can be solved using a simple approach. Here’s a Python implementation:

from typing import List

def max_profit(prices: List[int]) -> int:
    if not prices or len(prices) == 1:
        return 0

    max_profit = 0
    min_price = prices[0]

    for price in prices[1:]:
        # Update the minimum price if a lower price is encountered
        min_price = min(min_price, price)
        # Update the maximum profit if a higher selling price is encountered
        max_profit = max(max_profit, price - min_price)

    return max_profit

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

prices2 = [7, 6, 4, 3, 1]
print(max_profit(prices2))  # Output: 0

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input array prices.

Space Complexity:

The space complexity is O(1), as we use constant extra space.