2. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode

Time: O(n^2): TLE

Space: O(1)

var maxProfit = function (prices) {

    // TLE
    let profit = 0;
    for (let i = 0; i < prices.length; i++) {
        const buyPrice = prices[i];
        for (let j = i + 1; j < prices.length; j++) {
            const sellPrice = prices[j];
            const diff = sellPrice - buyPrice;
            profit = Math.max(diff, profit);
        }
    }
    
    return profit;
};

Time: O(n)

Space: O(n)

var maxProfit = function (prices) {
    let maxs = new Array(prices.length).fill(-Infinity);
    maxs[prices.length - 1] = prices[prices.length - 1];
    for (let i = prices.length - 2; i >= 0; i--) {
        maxs[i] = Math.max(maxs[i + 1], prices[i]);
    }

    let profit = 0;
    for (let i = 0; i < prices.length - 1; i++) {
        const buyPrice = prices[i];
        const sellPrice = maxs[i + 1];
        profit = Math.max(sellPrice - buyPrice, profit);
    }

    return profit;
};

Two pointer: best

Time: O(n)

Space: O(1)

var maxProfit = function (prices) {
    let profit = 0;

    let left = 0;
    let right = 1;
    while (right < prices.length) {
        if (prices[left] < prices[right]) {
            profit = Math.max(profit, prices[right] - prices[left]);
        } else {
            left = right;
        }

        right++;
    }

    return profit;
};