{x}
blog image

Best Time to Buy and Sell Stock

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.

 

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.

 

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Solution Explanation for Best Time to Buy and Sell Stock

This problem asks to find the maximum profit that can be obtained from buying and selling a stock once, given an array of stock prices for consecutive days. The key constraint is that you must buy before you sell.

Approach: Single Pass with Minimum Tracking

The most efficient approach is a single-pass algorithm that keeps track of the minimum price encountered so far. For each price, we calculate the potential profit by subtracting the minimum price from the current price. We update the maximum profit seen so far.

Algorithm:

  1. Initialization:

    • min_price: Initialize to the first price in the array. This variable will store the minimum price seen so far.
    • max_profit: Initialize to 0. This variable will store the maximum profit obtained.

  2. Iteration:

    • Iterate through the prices array starting from the second element (index 1).
    • For each price:
      • Update min_price to the minimum of min_price and the current price.
      • Calculate the current profit: profit = current_price - min_price.
      • Update max_profit to the maximum of max_profit and profit.

  3. Return: Return max_profit.

Time Complexity: O(n), where n is the number of prices in the array. We iterate through the array once.

Space Complexity: O(1). We use only a few constant extra variables.

Code Examples

The following code examples demonstrate the solution in multiple programming languages. They all implement the same algorithm described above.

Python:

def max_profit(prices):
    """
    Finds the maximum profit from buying and selling a stock once.
 
    Args:
        prices: A list of stock prices.
 
    Returns:
        The maximum profit, or 0 if no profit can be made.
    """
    min_price = prices[0]
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

Java:

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
}

C++:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int price : prices) {
            minPrice = min(minPrice, price);
            maxProfit = max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
};

JavaScript:

var maxProfit = function(prices) {
    let minPrice = prices[0];
    let maxProfit = 0;
    for (let price of prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }
    return maxProfit;
};

These examples illustrate the core algorithm. The specific syntax may vary slightly between languages, but the underlying logic remains the same. All the other languages provided in the original response follow a similar structure and efficiency.