Best Time To Buy and Sell Stock

leet code problem 121

Problem statement

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.

Solultion 1 , Unoptimized solution

This solution has timeout error because of O(n^2) time complexity due to double four loop iteration, with a large array it gets timeout arror and the test fails

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
       // set the initial max profit to zero
     let maxProfit =0;
    //iterate through each price
    for(let i=0;i<prices.length;i++){
        //compare the current day price with the prices that comes on the other days after it
        for(let j=i;j<prices.length;j++){
            console.log(i,j)
            let profit = prices[j]-prices[i]
            console.log(profit)
            //if a better price is found set the maximuProfit to it 
            if(profit>maxProfit){
                maxProfit = profit;
            }
        }
        console.log("-----",i)
    }
    //finally return the maxProfit
    return maxProfit;
};

Solution 2, Optimized

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

    for (let i = 1; i < prices.length; i++) {
        // If the current price is lower than the current minimum price,
        // update the minimum price
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        }
        // Calculate the potential profit and update the maximum profit
        else {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
    }

    return maxProfit;
};

Here's how the code works:

1. We initialize the maxProfit to 0 and the minPrice to the first price in the prices array.
2. We iterate through the prices array starting from the second element.
3. For each price, we check if it is lower than the current minPrice. If it is, we update the minPrice to the current price.
4. If the current price is not lower than the minPrice, we calculate the potential profit by subtracting the minPrice from the current price, and update the maxProfit to the maximum of the current maxProfit and the potential profit.
5. Finally, we return the maxProfit. The time complexity of this solution is O(n), where n is the length of the prices array, because we only need to iterate through the array once. The space complexity is O(1) because we only use a constant amount of extra space to store the maxProfit and minPrice variables.

The key difference between this solution and the first one is that we don't need to use a nested loop to compare the current price with all the future prices. Instead, we keep track of the minimum price seen so far, and update the maximum profit accordingly. This allows us to achieve a more efficient solution.