Best Time to Buy and Sell Stock easy

Problem Statement

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.

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 is 0.

Steps

1. Initialization: We need to track the minimum price encountered so far (minPrice) and the maximum profit (maxProfit). Initialize minPrice to the first price in the array, and maxProfit to 0.

2. Iteration: Iterate through the prices array, starting from the second element.

3. Comparison: For each price, compare it with the current minPrice.

   • If the current price is less than minPrice, update minPrice to the current price (because we've found a potentially better day to buy).
   • If the current price is greater than or equal to minPrice, calculate the potential profit (currentProfit = price - minPrice). Update maxProfit if currentProfit is greater.

4. Return: After iterating through all prices, return maxProfit.

Explanation

The algorithm efficiently finds the maximum profit by keeping track of the minimum buying price encountered so far. At each step, it checks if selling at the current price would yield a higher profit than the current maximum profit. This avoids the need to check all possible buy-sell combinations, resulting in a linear time complexity solution.

Code

function maxProfit(prices: number[]): number {
    let minPrice: number = prices[0];
    let maxProfit: number = 0;

    for (let i = 1; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            const currentProfit = prices[i] - minPrice;
            maxProfit = Math.max(maxProfit, currentProfit);
        }
    }

    return maxProfit;
};

Complexity

• Time Complexity: O(n), where n is the number of prices in the input array. We iterate through the array once.
• Space Complexity: O(1). We only use a constant amount of extra space to store minPrice and maxProfit.