[Leetcode] Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

You are given an array priceswhere prices[i]is the price of a given stock on the i``thday.

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 <= 10``5

0 <= prices[i] <= 10``4

How to appoach?

Brute Force

function maxProfit(prices: number[]): number {
    let maxprofit = 0;
    for (let i = 0; i < prices.length - 1; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            let profit = prices[j] - prices[i];
            if (profit > maxprofit) maxprofit = profit;
        }
    }
    return maxprofit;
}

1. set maxProfit as 0.
2. create for loop using i and j, j will have the starting point for other elements after i index.
3. profit will be the subtract j index element from i index element.
4. and if profit is bigger than max profit then use profit as max profit.
5. return the max profit at the end.

summary

this checked all the possible profits from elements. and compare them. time limit exceeded.

One Pass

function maxProfit(prices: number[]): number {
    let minprice = Number.MAX_VALUE;
    let maxprofit = 0;
    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < minprice) minprice = prices[i];
        else if (prices[i] - minprice > maxprofit)
            maxprofit = prices[i] - minprice;
    }
    return maxprofit;
}

1. set min price as the biggest number in js.
2. and set max profit as 0.
3. in for loop, it will check the i index price and compare it to min price, and if current price is cheaper than min price then set it as new min price.
4. but if the current profit is bigger than max profit then max profit will be the current profit which is current price - min price.
5. lastly return the max profit.

summary

this is using 2 variables, and check it with every i index element(current price).

use this way, it will have O(n) time c and O(1) space c.