Best Time to Buy and Sell Stock

Problem Description

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.

Key Insights

• You can only complete one buy-sell transaction.
• The goal is to find the maximum profit from buying at a lower price and selling at a higher price later.
• The optimal solution requires tracking the minimum price encountered so far while iterating through the list.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves a single pass through the prices array while maintaining two variables: one for the minimum price encountered so far (min_price) and another for the maximum profit possible (max_profit). As you iterate through the prices:

1. Update the min_price if the current price is lower.
2. Calculate the potential profit by subtracting min_price from the current price.
3. Update max_profit if the potential profit is higher than the previously recorded maximum profit.

This approach ensures that we only traverse the list once, making it efficient.

Code Solutions